Guided Policy

The GuidedPolicy class is the core class of the main path guided exploration strategy. It is mainly responsible for obtaining the main path defined by the user when defining properties and generating input events based on the main path guided exploration strategy. This class provides a complete guiding method for the event generation process of the main path guided exploration strategy. The main methods included in GuidedPolicy are:

  • Randomly select a main path from the user-defined main paths before starting a test.

  • Determine the type of event to return based on whether the current state is on the main path.

  • Get the next event to execute on the main path.

  • The main control of exploring the application’s deep state process after leaving the main path.

  • Obtain events from the main path that can guide the application back to the main path.

Introduction to the main path guided strategy

It has been observed that when users specify the properties of applications, they typically reach the target application functions along the main path from the entry point. Such primary paths can be easily obtained and used to guide exploration. Specifically, when executing the main path from the application entry, we can obtain a series of GUI states: \(S = [s_0,s_1,s_2,……,s_n]\), where \(s_n \models P\), meaning \(s_n\) meets the preconditions. In addition, exploring states close to the main path may have a higher chance of reaching GUI states that meet the preconditions. The core execution process of this algorithm is illustrated in the figure.

../../_images/mainpath_flowchart.png

Flowchart of the main path guided exploration strategy

The specific execution steps are as follows:

Step 1: Send each event :math: e_i from the main path to the mobile application under test, obtaining the state sequence of the main path \(S = [s_0,s_1,s_2,……,s_n]\), thus making the mobile application under test reach the state \(s_n\) that satisfies the precondition \(P\).

Step 2: Determine whether the maximum test execution time has been reached; if so, end the test; otherwise, explore the application in reverse order according to \(S = [s_0,s_1,s_2,……,s_n]\). If all states in \(S\) have been explored, initialize the mobile application under test; otherwise, retrieve an unexplored state \(s_i\) according to the reverse relationship, send the corresponding prefix event sequence \([e_1,e_2,……,e_i]\) to make the mobile application under test reach the main path state \(s_i\), and continue to step 3;

Step 3: Use state \(s_i\) as the starting state to explore the mobile application under test, determining whether the number of events executed so far has reached the maximum number of events; if not, obtain the current state of the mobile application under test and continue to step 4; if it has, execute step 6;

Step 4: Determine whether the current state of the mobile application under test satisfies one or more preconditions \(P\). If no preconditions are met or if no property check is performed, continue to step 5; otherwise, execute the event sequence defined in the interactive scenario \(I\), check whether the postcondition \(Q\) is satisfied, and return to step 3;

Step 5: Use external user interface interaction tools to analyze the current interface state to obtain a list of executable events, randomly select one event from the list of executable events, and send it to the mobile application under test to execute, then return to step 3;

Step 6: Determine whether the current state can be transformed into state \(s_n\); if so, send the corresponding event to the mobile application under test to ensure that the state of the mobile application meets the precondition;

To present the above process of the strategy more clearly, the following figure further analyzes this process.

../../_images/mainpath_implementation_diagram.png

Schematic diagram of the implementation of the main path guided exploration strategy

Let \(s_0\) be the starting exploration state of the mobile application under test, and the main path be \(E = [e_1,e_2,e_3,e_4]\), with properties \(\phi = <P,I,Q>\). In the first iteration, this strategy will send all events of :math: E and reach \(s_4\), where \(s_4 \models P\). States satisfying \(P\) are marked in gray. Then the strategy guides random exploration starting from \(s_4\). Assume it generates \(e_5\) at \(s_4\) and reaches \(s_5\). Suppose \(s_5 \models P\), the strategy may decide to execute \(I\) to obtain the end state \(s_6\) and check postcondition \(Q\) at this state. If \(s_6 \models P\), it indicates no property errors found. At this point, if the number of executed events of \(e_5\) and \(I\) exceeds the predefined maximum event count, the strategy will stop random exploration and attempt to navigate to the main path satisfying \(P\). If events in \(E\) cannot be sent at \(s_6\), this strategy will abandon the guiding process and start the second iteration. In the second and third iterations, it will start from \(s_3\) and \(s_2\), respectively, and perform a process similar to the first iteration. In the fourth iteration, it starts from \(s_1\). Assume that during the process two random events \(e_6\) and \(e_7\) are generated to explore \(s_1\), \(e_6 \to s_7\), \(e_7 \to s_8\), but both \(s_7\) and \(s_8\) do not satisfy the precondition \(P\), then this strategy attempts to navigate back to follow the main path that satisfies \(P\). Assume that during the process it finds that \(e_3\) can be sent at \(s_8\). It will sequentially send \(e_3\) and \(e_4\) to attempt to follow the main path. Finally, it reaches \(s_4\) satisfying \(P\), and this strategy will execute \(I\) and check postcondition \(Q\) at the end state \(s_9\). If the postcondition is not satisfied, it indicates the discovery of a functional property error.

Step 7: Check whether the current state meets the preconditions; if it does, perform property testing;

Step 8: Restart the mobile application and return to step 2.

Default parameters

  • MAX_NUM_RESTARTS: Maximum number of restarts.

  • MAX_NUM_STEPS_OUTSIDE: Maximum number of steps outside the application.

  • MAX_NUM_STEPS_OUTSIDE_KILL: Maximum number of steps outside the application (forced termination).

  • START_TO_GENERATE_EVENT_IN_POLICY: Start time of event generation in the policy.

  • MAX_NUM_QUERY_LLM: Maximum number of queries to LLM.

  • EVENT_FLAG_STARTED: Event start flag.

  • EVENT_FLAG_START_APP: Event flag for starting the application.

  • EVENT_FLAG_STOP_APP: Event flag for stopping the application.

  • EVENT_FLAG_EXPLORE: Exploration event flag.

  • EVENT_FLAG_NAVIGATE: Navigation event flag.

  • EVENT_FLAG_TOUCH: Touch event flag.

  • POLICY_GUIDED: Name of the main path guided strategy.

  • POLICY_RANDOM: Name of the random strategy.

  • POLICY_LLM: Name of the LLM strategy.

  • POLICY_NONE: Name of no strategy.

Data structures in the GuidedPolicy class

  1. main_path

    main_path is an object of the MainPath class, representing the main path chosen for the current testing process.

  2. execute_main_path

    execute_main_path is a boolean that records whether the current interface state is on the main path. It is used to generate different events based on different situations.

  3. current_index_on_main_path

    current_index_on_main_path is an integer that represents the event node number of the current position on the main path. Its initial value is 0.

  4. current_number_of_mutate_steps_on_single_node

    current_number_of_mutate_steps_on_single_node is an integer that records the number of times events have been explored and generated at the current state node. Its initial value is 0.

  5. max_number_of_mutate_steps_on_single_node

    max_number_of_mutate_steps_on_single_node is an integer that records the maximum number of exploration and event generation attempts for a single state node. Its initial value is 20.

  6. number_of_events_that_try_to_find_event_on_main_path

    number_of_events_that_try_to_find_event_on_main_path is an integer that records the current number of attempts to return to the main path. Its initial value is 0.

  7. index_on_main_path_after_mutation

    index_on_main_path_after_mutation is an integer representing the event number on the main path that can be returned to after executing a series of event explorations on a specific state node. Its initial value is -1.

  8. mutate_node_index_on_main_path

    mutate_node_index_on_main_path is an integer that records the event node number on the current explored main path. Its initial value is the length of the selected main path.

Pseudocode for the main path guided strategy

\(\textbf{Algorithm:} Main Path Guided Exploration\)

\(\textbf{Input:} \phi = <P,I,Q>,E=[e_1,e_2,……,e_n]\)

\(\textbf{Output:} Bug Report\)

 1Function main (Φ = <P,I,Q>, E = [e1,e2,……,en])
 2    i ← n;
 3    while not timeout do
 4        if i > 0 then
 5            for e ← e1  to ei  do
 6                sendEventToApp (e);
 7        explore(Φ,E)
 8        i ← i-1
 9        if i = -1 then
10            cleanApp();
11            i ← n;
12        restartApp();
13Function explore (Φ = <P,I,Q>, E = [e1,e2,……,en])
14    for t < 1 to MAX_STEP do
15        s ← getCurrentState();
16        if s ⊨ P ∧ random() < 0.5 then
17            checkProperty(I,Q) ;
18        else
19            e ← generateRandomEvent (s);
20            sendEventToApp(e);
21    ej  ← canGoToSatisfyPrecondition(E);
22    if ej  ≠ null then
23        goToSatisfyPrecondition (e_j,E);
24    s ← getCurrentState();
25    if s ⊨ P then
26        checkProperty (I,Q) ;
27Function canGoToSatisfyPrecondition (E = [e1,e2,……,en]):
28    s ← getCurrentState();
29    for ej  ← en  to e1  do
30        if ej  ← en  to e1  then
31            return ej;
32     return null;
33Function goToSatisfyPrecondition(ej, E = [e_1,e_2,……,e_n]):
34    for e ← ej  to en  do
35        s ← getCurrentState();
36        if e.widget ∈ s then
37            sendEventToApp(e);

This strategy adopts a main path in the form of an input property \(\phi = <P,I,Q>\) and an event sequence \(E = [e_1,e_2,……,e_n]\). The strategy traverses backward along the main path and conducts UI exploration within the proximity of the main path (lines 3-12). Specifically, it iterates from \(e_n\) backward to \(e_1\) (line 8). For each event \(e_i\) where \(0 < i \leq n\), it sends the prefix \([e_1,e_2,……,e_i]\) to the application to reach the GUI state on the main path \(s_i\) (lines 5-6). Next, it explores the GUI states close to \(s_i\), attempting to find states that satisfy the precondition \(P\) (line 7). Note that after \(s_1\), this system also explores GUI states close to \(s_0\) by not sending any events from \(E\) (line 4). If time budget permits, multiple traversals can be made along the main path, and after exploring each state on the main path (lines 9-11), application data will be cleaned.

Exploration starting from the GUI state of the main path is similar to the aforementioned random exploration strategy (lines 14-20). Specifically, in each GUI state, this algorithm checks for the satisfaction of a certain precondition \(P\) (lines 15-16). If a precondition is met, the algorithm has a 50% probability of testing the property at \(s\) (line 16). Otherwise, it will generate random events and send them to the device to reach another state (lines 19-20). The aforementioned process iterates \(MAX_STEP\) times (line 14).

After exploration is complete, this algorithm attempts to return to states that meet the preconditions (lines 21-23). Since random exploration starting from the GUI state of the main path may change the internal state of the application, in such cases, reaching states that meet the preconditions might exhibit different behaviors further. To this end, this algorithm searches for the nearest event \(e_j\) that can be sent in the current GUI state (lines 28-32). If \(e_j\) exists, we attempt to send the suffix \([e_j,e_j+1,……,e_n]\) of \(E\) to the device (lines 34-37). Finally, we attempt to test the application properties again (lines 24-26).

Member methods in the GuidedPolicy class

Note

To facilitate readers’ understanding, the simplified version of the code snippets provided in this paper only abstracts and showcases the core processes, and the actual code may not completely align with the simplified reference code.

Methods for obtaining the main path

  1. select_main_path

    select_main_path randomly selects a main path from all user-defined main paths as the guiding path for this round of testing.

    def select_main_path(self):
    if len(self.kea.all_mainPaths) == 0:
        self.logger.error("No mainPath")
        return
    self.main_path = random.choice(self.kea.all_mainPaths)
    self.path_func, self.main_path = self.main_path.function, self.main_path.path
    self.main_path_list = copy.deepcopy(self.main_path)
    self.max_number_of_events_that_try_to_find_event_on_main_path = min(10, len(self.main_path))
    self.mutate_node_index_on_main_path = len(self.main_path)

Member methods of event generation management

  1. generate_event

    A method for determining which events should be generated based on the current application state. If outside the application, it returns to the application; if in the initial stage, it runs the initialization function; if executing the main path, it returns main path events; if exploring the application, it returns events needed to continue exploration.

    Parameters:

    • None

    Returns:

    • A generated event.

    def generate_event(self):
    current_state = self.from_state
    event = self.move_the_app_to_foreground_if_needed(current_state)
    if event is not None:
        return event
    if (self.event_count == START_TO_GENERATE_EVENT_IN_POLICY and self.current_index_on_main_path == 0)
    or isinstance(self.last_event, ReInstallAppEvent):
        self.select_main_path()
        self.run_initializer()
        self.from_state = self.device.get_current_state()
    if self.execute_main_path:
        event_str = self.get_next_event_from_main_path()
        if event_str:
            self.kea.execute_event_from_main_path(event_str)
            return None
    if event is None:
        event = self.mutate_the_main_path()
    return event

Member methods for obtaining events on the main path

  1. get_next_event_from_main_path

    Get the next event to be executed on the main path.

    Parameters:

    • None

    Returns:

    • The next event on the main path.

    def get_next_event_from_main_path(self):
    if self.current_index_on_main_path == self.mutate_node_index_on_main_path:
        self.execute_main_path = False
        return None
    u2_event_str = self.main_path_list[self.current_index_on_main_path]
    if u2_event_str is None:
        self.current_index_on_main_path += 1
        return self.get_next_event_from_main_path()
    self.current_index_on_main_path += 1
    return u2_event_str

Member methods of application state exploration process

  1. mutate_the_main_path

    Determine whether to continue generating random events or return to the main path based on the current number of event executions.

    Parameters:

    • None

    Returns:

    • Events generated after exploration.

    def mutate_the_main_path(self):
    event = None
    self.current_number_of_mutate_steps_on_single_node += 1
    if (self.current_number_of_mutate_steps_on_single_node >= self.max_number_of_mutate_steps_on_single_node):
        if (self.number_of_events_that_try_to_find_event_on_main_path <= self.max_number_of_events_that_try_to_find_event_on_main_path):
            self.number_of_events_that_try_to_find_event_on_main_path += 1
            if self.index_on_main_path_after_mutation == len(self.main_path_list):
                rules_to_check = (self.kea.get_rules_whose_preconditions_are_satisfied())
                if len(rules_to_check) > 0:
                    t = self.time_recoder.get_time_duration()
                    self.time_needed_to_satisfy_precondition.append(t)
                    self.check_rule_whose_precondition_are_satisfied()
                return self.stop_mutation()
            event_str = self.get_event_from_main_path()
            try:
                self.kea.execute_event_from_main_path(event_str)
                return None
            except Exception:
                return self.stop_mutation()
        return self.stop_mutation()
    self.index_on_main_path_after_mutation = -1
    if len(self.kea.get_rules_whose_preconditions_are_satisfied()) > 0:
        self.check_rule_whose_precondition_are_satisfied()
        return None
    event = self.generate_random_event_based_on_current_state()
    return event

  2. generate_random_event_based_on_current_state

    Generate random events to explore the application.

    Parameters:

    • None

    Returns:

    • Randomly generated event.

    def generate_random_event_based_on_current_state(self):
    current_state = self.from_state
    event = self.move_the_app_to_foreground_if_needed(current_state)
    if event is not None:
        return event
    possible_events = current_state.get_possible_input()
    possible_events.append(KeyEvent(name="BACK"))
    possible_events.append(RotateDevice())
    self._event_trace += EVENT_FLAG_EXPLORE
    event = random.choice(possible_events)
    return event

  3. stop_mutation

    Stop the exploration process and reset parameters.

    Parameters:

    • None

    Returns:

    • Restart or reinstall application events.

    def stop_mutation(self):
    self.index_on_main_path_after_mutation = -1
    self.number_of_events_that_try_to_find_event_on_main_path = 0
    self.execute_main_path = True
    self.current_number_of_mutate_steps_on_single_node = 0
    self.current_index_on_main_path = 0
    self.mutate_node_index_on_main_path -= 1
    if self.mutate_node_index_on_main_path == -1:
        self.mutate_node_index_on_main_path = len(self.main_path)
        return ReInstallAppEvent(app=self.app)
    return KillAndRestartAppEvent(app=self.app)

Member methods for returning to the main path from the exploration process

  1. get_event_from_main_path

    Depending on whether the current state has returned to the main path, if it has returned, execute the subsequent main path events; if it hasn’t returned to the main path, attempt to return to the main path in reverse order based on the main path event sequence.

    Parameters:

    • None

    Returns:

    • Main path event string.

    def get_event_from_main_path(self):
    if self.index_on_main_path_after_mutation == -1:
        for i in range(len(self.main_path_list) - 1, -1, -1):
            event_str = self.main_path_list[i]
            ui_elements_dict = self.get_ui_element_dict(event_str)
            current_state = self.from_state
            view = current_state.get_view_by_attribute(ui_elements_dict)
            if view is None:
                continue
            self.index_on_main_path_after_mutation = i + 1
            return event_str
    else:
        event_str = self.main_path_list[self.index_on_main_path_after_mutation]
        ui_elements_dict = self.get_ui_element_dict(event_str)
        current_state = self.from_state
        view = current_state.get_view_by_attribute(ui_elements_dict)
        if view is None:
            return None
        self.index_on_main_path_after_mutation += 1
        return event_str
    return None

  2. get_ui_element_dict

    Get relevant information about the components operated on by a single event on the main path.

    Parameters:

    • ui_element_str: Component information string

    Returns:

    • Dictionary form of the relevant information for that component.

    def get_ui_element_dict(self, ui_element_str: str) -> Dict[str, str]:
    start_index = ui_element_str.find("(") + 1
    end_index = ui_element_str.find(")", start_index)
    if start_index != -1 and end_index != -1:
        ui_element_str = ui_element_str[start_index:end_index]
    ui_elements = ui_element_str.split(",")
    ui_elements_dict = {}
    for ui_element in ui_elements:
        attribute_name, attribute_value = ui_element.split("=")
        attribute_name = attribute_name.strip()
        attribute_value = attribute_value.strip()
        attribute_value = attribute_value.strip('"')
        ui_elements_dict[attribute_name] = attribute_value
    return ui_elements_dict