Patent Publication Number: US-10783061-B2

Title: Reducing likelihood of cycles in user interface testing

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     N/A 
     BACKGROUND 
     An application is a computer program that is designed to perform a group of coordinated functions, tasks, or activities. Applications are sometimes referred to as “apps,” especially if they are built for mobile platforms. There are many different types of applications in use today, including word processors, spreadsheets, presentation programs, calendars, web browsers, email clients, messaging apps, media players, video games, photo editors, social media apps, and so forth. 
     A user interacts with an application via a user interface. Most modern applications have graphical user interfaces (GUI), which include graphical elements such as navigational controls (e.g., navigational panels, context menus, control ribbons), input controls (e.g., checkboxes, radio buttons, dropdown lists), and informational components (e.g., progress bars, message boxes). User actions in a GUI are usually performed through direct manipulation of the graphical elements. The content of a GUI may be organized into multiple pages, and a user may navigate between the various pages through the use of the navigational controls that exist within the GUI. 
     The user interface of an application may be tested to verify that the various elements of the user interface function as intended. Testing may provide information about errors and other issues that may detrimentally affect a user&#39;s experience with the application. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates a system for testing a user interface of an application in accordance with the present disclosure. 
         FIG. 2  illustrates an example showing various pages that may be included in a user interface for an application. 
         FIG. 3  illustrates an example of a finite state machine representation of the user interface whose pages are shown in  FIG. 2 . 
         FIG. 4  illustrates an example of certain paths that the testing program may explore in its testing of the user interface. 
         FIG. 5A  illustrates a portion of a data structure that may be used to define costs that are associated with particular state transitions. 
         FIGS. 5B-5F  illustrate portions of a data structure that may be used to maintain tallies indicating the total cost that has been incurred during particular tests. 
         FIG. 6  illustrates a testing environment in which the testing of a user interface is distributed across multiple computer systems. 
         FIG. 7  illustrates an example of a method for testing a user interface of an application in accordance with the present disclosure. 
         FIG. 8  illustrates certain components that may be included within a computer system. 
     
    
    
     DETAILED DESCRIPTION 
     User interface testing is often a bottleneck in the long-term development cycle of an application. One known testing framework involves recording actual user interactions with the user interface of an application and then replaying those interactions during a testing stage. This type of approach, however, is not methodical. It is also not targeted to important aspects of the user interface, and as a result many important aspects of the user interface may remain untested. Also, because the set of tests that are performed on the user interface are manually created, this type of testing is essentially static and cannot be easily adapted to test parts of the user interface that may be subsequently changed or added. 
     Another known framework for testing user interfaces is sometimes referred to as “monkey testing.” This testing framework, which is typically designed to facilitate stress testing (i.e., testing the user interface beyond the limits of normal operation), involves having a testing program randomly generate coordinates and simulate different types of user interactions based on those coordinates. Again, however, this type of testing is not methodical or targeted to important aspects of the user interface, and as a result many important aspects of the user interface may remain untested. Moreover, under some circumstances the testing program may enter into cycles where the same parts of the user interface are repeatedly tested, which wastes testing resources. Another problem is that randomly generated user interactions may activate hyperlinks to external locations, thereby causing the testing program to shift its focus from the application under test to websites or other applications. 
     The techniques disclosed herein enable more thorough testing of a user interface than is possible with known approaches. In accordance with the present disclosure, a user interface of an application may be represented as a finite state machine having multiple states and various transitions between the states. Some of the states and state transitions may be tested systematically, while other states and state transitions may be selectively tested. Where selective testing is used, paths that lead to cycles or redundant paths may be penalized. This causes more frequent traversal of new paths, thus leading toward more complete testing of the user interface. 
       FIG. 1  illustrates a system  100  for testing a user interface  102  of an application  104  in accordance with the present disclosure. A finite state machine (FSM) representation  106  of the user interface  102  may be created. The FSM representation  106  may define possible states  108  and possible state transitions  110  of the user interface  102 . In this context, the term “state” may refer to a particular condition of the user interface  102 , which may be described in terms of the page(s) and/or other elements of the user interface  102  that are being displayed to the user. The term “state transition” may refer to a change from one state to another. 
     Broadly speaking, the states  108  and state transitions  110  in the FSM representation  106  may be divided into two categories: (i) states  108  and state transitions  110  that are of highest importance and should be tested systematically, and (ii) states  108  and state transitions  110  that are of lesser importance and can be selectively tested. In accordance with the present disclosure, a testing program  112  may be configured to explore all of the states  108  and state transitions  110  in category (i), but may only explore a subset of the states  108  and state transitions  110  in category (ii). 
     As part of exploring the subset of the states  108  and state transitions  110  in category (ii), the testing program  112  may be configured to penalize paths that lead to cycles. In this context, the term “path” may refer to a sequence of states  108  and state transitions  110  that the testing program  112  may explore when it performs testing. The term “cycle” may refer to a path that is repeated multiple times. The term “explore” refers to one or more actions that may be taken to investigate aspects of the user interface  102 . For example, the testing program  112  explores a particular state  108  when it causes the user interface  102  to navigate to that state  108 . The testing program  112  explores a particular state transition  110  when it activates one or more elements of the user interface  102  in order to cause that state transition  110  to occur. 
     It is generally desirable to prevent the testing program  112  from entering cycles to the extent possible. In a user interface  102  of average complexity, there may be a very large number (e.g., millions) of paths that may be traversed among the various states  108  and state transitions  110 . Given the amount of time that is typically available for testing, it is generally not possible to test all of these paths. It is, however, desirable to test as many of these paths as possible. By penalizing paths that lead to cycles, the testing program  112  may be able to maximize the number of unique paths that are tested, thereby increasing the effectiveness of the testing and the usefulness of the testing results. 
     The testing program  112  may utilize various data structures  114  to keep track of information that makes it possible to penalize paths that are susceptible to cycles. These data structures  114  may operate to bias the testing program  112  away from paths that are susceptible to cycles. In some implementations, the data structures  114  may define costs that are associated with particular state transitions  110 . State transitions  110  that are less susceptible to cycles may be associated with more favorable costs than the state transitions  110  that are more susceptible to cycles. The data structures  114  may also maintain tallies indicating the total cost that has been incurred during particular tests. The testing program  112  may be configured to select state transitions  110  in a probabilistic manner based on the associated costs. Some examples of these data structures  114  and how they may be used to penalize certain paths and to favor other paths will be described below. 
     If errors  116  (e.g., crash events) are detected during testing, the testing program  112  may record the errors  116  in a log  118 . The entries in the log  118  may be made available to interested parties, such as developers of the application  104 , who may use this information to improve the user interface  102  by correcting the errors  116  that are discovered. 
       FIG. 2  illustrates an example showing various pages  220  that may be included in a user interface  102  for an application  104 . The user interface  102  may include a home page  220   a , which may be the main page of the user interface  102 . The home page  220   a  may include links  222   a - d  (e.g., hyperlinks) that facilitate navigation to other pages  220  of the user interface  102 . In the depicted example, the home page  220   a  includes a link  222   a  to a favorites page  220   b , a link  222   b  to a search page  220   c , a link  222   c  to a history page  220   d , and a link  222   d  to a news page  220   e.    
     In the depicted example, the favorites page  220   b  includes a link  222   e  to another page that will be referred to as page F 1   220   f . Page F 1   220   f  includes a link  222   f  back to the favorites page  220   b  and a link  222   g  to another page that will be referred to as page F 2   220   g . Page F 2   220   g  includes a link  222   h  to another page that will be referred to as page F 3   220   h . Page F 2   220   g  also includes a link  222   i  back to the home page  220   a . Page F 3   220   h  may include one or more links  222   j  to one or more other pages  220   l.    
     The search page  220   c  includes one or more links  222   k  to one or more other pages  220   m . Similarly, the history page  220   d  includes one or more links  222   l  to one or more other pages  220   n.    
     The news page  220   e  includes a link  222   m  to a page that will be referred to as page N 1   220   i , a link  222   n  to a page that will be referred to as page N 2   220   j , and a link  222   o  to a page that will be referred to as page N 3   220   k . These pages  220   i - k  include links  222   p - r  to other pages  220   o.    
     The pages  220  of the user interface  102  may include other links in addition to those that are specifically shown in  FIG. 2 . For example, some or all of the pages  220  may include a link back to the home page  220   a.    
     For the sake of clarity, the depicted user interface  102  is relatively simple in that it only includes a few pages  220 . This, however, should not be interpreted as limiting the scope of the present disclosure. The inventive principles disclosed herein are applicable to user interfaces of varying degrees of complexity, including user interfaces that are much more complex (or less complex) than those discussed herein. 
       FIG. 3  illustrates an example of an FSM representation of the user interface  102  whose pages  220  are shown in  FIG. 2 . The FSM representation is depicted as a graph with nodes corresponding to the states  308  of the user interface  102  and edges corresponding to state transitions  310 . The states  308  may correspond to different pages  220  of the user interface  102 . For example, a home state  308   a  may correspond to a condition of the user interface  102  in which the home page  220   a  is displayed, a favorites state  308   b  may correspond to a condition of the user interface  102  in which the favorites page  220   b  is displayed, and so forth. Other states  308  that are shown in  FIG. 3  include a search state  308   c  (corresponding to the search page  220   c ), a history state  308   d  (corresponding to the history page  220   d ), a news state  308   e  (corresponding to the news page  220   e ), a page F 1  state  308   f  (corresponding to page F 1   220   f ), a page F 2  state  308   g  (corresponding to page F 2   220   g ), a page F 3  state  308   h  (corresponding to page F 3   220   h ), a page N 1  state  308   i  (corresponding to page N 1   220   i ), a page N 2  state  308   j  (corresponding to page N 2   220   j ), and a page N 3  state  308   k  (corresponding to page N 3   220   k ). 
     The testing program  112  may initiate a state transition  310  by activating one or more elements of the user interface  102 . For example, when the user interface  102  is in the home state  308   a , the testing program  112  may activate the link  222   a  to the favorites page  220   b  in order to transition from the home state  308   a  (in which the home page  220   a  is displayed) to the favorites state  308   b  (in which the favorites page  220   b  is displayed). 
     Each of the states  308  may be associated with a particular depth. In this context, the term “depth” may indicate the position of a particular state  308  relative to the home state  308   a . For example, in some implementations, the home state  308   a  may be associated with a depth of one. The states  308   b - e  that are only one transition  310  away from the home state  308   a  (namely, the favorites state  308   b , the search state  308   c , the history state  308   d , and the news state  308   e  in the depicted example) may be associated with a depth of two. The states  308   f - k  that are more than one transition  310  away from the home state  308   a  may be associated with a depth that is greater than two. 
     A critical depth  324  for testing the user interface  102  may be determined. In this context, the term “critical depth” refers to a point of differentiation between systematic testing and selective testing. In other words, the states  308  and state transitions  310  of the user interface  102  that are within the critical depth  324  may be tested differently than the states  308  and state transitions  310  of the user interface  102  that are beyond the critical depth  324 . In some implementations, the testing program  112  may be configured to explore all of the states  308  and the state transitions  310  that are within the critical depth  324 . In contrast, the testing program  112  may be configured to only explore a subset of the states  308  and the state transitions  310  that are beyond the critical depth  324 . 
     In the depicted example, the critical depth  324  is two. Therefore, the home state  308   a , the favorites state  308   b , the search state  308   c , the history state  308   d , and the news state  308   e , as well as the transitions  310  between these states  308   a - e , are within the critical depth  324 . Thus, the testing program  112  may be configured to explore all of these states  308   a - e  and state transitions  310 . The other states  308   f - k  and state transitions  310  are beyond the critical depth  324 . Consequently, the testing program  112  may be configured so that it only explores a subset of these states  308   f - k  and state transitions  310 . 
     Although the critical depth  324  in the depicted example is two, this should not be interpreted as limiting the scope of the present disclosure. The critical depth  324  may be a different value. Also, the critical depth  324  may be configurable. For example, a user of the testing program  112  may adjust the critical depth  324  as desired. 
     As indicated above, the testing program  112  may be configured to penalize paths that lead to cycles.  FIG. 4  illustrates an example of certain paths that the testing program  112  may explore in its testing of the user interface  102 . In this example, starting from the home state  408   a  (in which the home page  220   a  is displayed), the testing program  112  may activate the link  222   a  to the favorites page  220   b , thereby causing a transition  410   a  to the favorites state  408   b  (in which the favorites page  220   b  is displayed). Next, on the favorites page  220   b , the testing program  112  may activate the link  222   e  to page F 1   220   f , thereby causing a transition  410   b  to the page F 1  state  408   f  (in which page F 1   220   f  is displayed). Next, on page F 1   220   f , the testing program  112  may activate the link  222   g  to page F 2   220   g , thereby causing a transition  410   c  to the page F 2  state  408   g  (in which page F 2   220   g  is displayed). Next, on page F 2   220   g , the testing program  112  may activate the link  222   h  to page F 3   220   h , thereby causing a transition  410   d  to the page F 3  state  408   h  (in which page F 3   220   h  is displayed). 
     It is possible that at some point the testing program  112  may enter a cycle as it tests the user interface  102 . In other words, it is possible that the testing program  112  may follow the same path multiple times. A simple example of a cycle involves alternating between two states. For example, when the user interface  102  is in the favorites state  408   b , the testing program  112  may activate the link  222   e  to page F 1   220   f , thereby causing the user interface  102  to transition  410   b  to the page F 1  state  408   f . However, when the user interface  102  is in the page F 1  state  408   f , the testing program  112  may activate the link  222   f  to the favorites page  220   b , thereby causing the user interface  102  to transition  410   e  back to the favorites state  408   b . Under some circumstances, this simple cycle between the favorites state  408   b  and the page F 1  state  408   f  may be repeated multiple times. 
     A more complicated example of a cycle involves repeating a path that includes several states and state transitions. For example, suppose that the testing program  112  explores the following path: home state  408   a  favorites state  408   b  page F 1  state  408   f  page F 2  state  408   g , as discussed above. There may be two possible transitions  410   d ,  410   f  out of the page F 2  state  408   g . One possible transition  410   d  was discussed previously: the testing program  112  may activate the link  222   h  to page F 3   220   h , thereby causing a transition  410   d  to the page F 3  state  408   h . Alternatively, however, the testing program  112  may activate the link  222   i  to the home page  220   a , thereby causing a transition  410   f  to the home state  408   a . If this happens, then it is possible that the testing program  112  will repeat the path that it has just explored (i.e., home state  408   a  favorites state  408   b  page F 1  state  408   f  page F 2  state  408   g ). It is also possible that this path may be repeated multiple times. 
     To reduce the likelihood that the testing program  112  will enter a cycle as it tests the user interface  102 , the testing program  112  may be configured to penalize paths that are susceptible to cycles. To facilitate this, the testing program  112  may keep track of certain information that may be used to encourage certain paths and discourage others. More specifically, whenever there are multiple states to choose from in the part of the user interface  102  that is beyond the critical depth  324 , the testing program  112  may be configured to select one of the possible next states based on probabilities that are associated with transitions to those possible next states. The probability that is associated with the transition to a particular state may be related to the likelihood that the transition could lead to a cycle. 
     Continuing with the above example, suppose that the testing program  112  is in the page F 2  state  408   g  and is choosing between transitioning  410   d  from the page F 2  state  408   g  to the page F 3  state  408   h , or transitioning  410   f  from the page F 2  state  408   g  to the home state  408   a . The testing program  112  may select one of these options based on probabilities associated with these transitions  410   d ,  410   f . The probability associated with a particular transition may be related to the likelihood that the selection of that transition could lead to a cycle. In this example, the transition  410   d  from the page F 2  state  408   g  to the page F 3  state  408   h  is less likely to lead to a cycle than the transition  410   f  from the page F 2  state  408   g  to the home state  408   a . Therefore, the transition  410   d  from the page F 2  state  408   g  to the page F 3  state  408   h  may be associated with a higher probability than the transition  410   f  from the page F 2  state  408   g  to the home state  408   a . In other words, the testing program  112  may be configured so that there is a higher probability of selecting the transition  410   d  from the page F 2  state  408   g  to the page F 3  state  408   h  than of selecting the transition  410   f  from the page F 2  state  408   g  to the home state  408   a.    
     A specific example illustrating how these probabilities may be assigned will now be discussed. In this example, at least two data structures may be used to keep track of certain information that makes it possible to penalize paths that are susceptible to cycles. A first data structure may define costs associated with transitioning between different states. A second data structure may maintain tallies indicating the total costs that have been incurred during a particular test. In some implementations, these data structures may be implemented as matrices. A matrix that defines the costs associated with transitioning between different states may be referred to herein as an adjacency matrix. A matrix that maintains the tallies indicating total costs of traversal may be referred to herein as a cost matrix. A portion of an adjacency matrix  526  is shown in  FIG. 5A . Portions of a cost matrix  528  are shown in  FIGS. 5B-5F . 
     Referring to  FIG. 5A , the adjacency matrix  526  may define costs for all of the state transitions that are possible in the user interface  102 . These costs may be determined in advance of testing by individuals who are familiar with the user interface  102  and who know which paths are susceptible to cycles. 
     In the depicted example, the rows of the adjacency matrix  526  indicate the starting point of a state transition, and the columns of the adjacency matrix  526  indicate the ending point of a state transition. Thus, the cell  530   a  indicates the cost associated with a transition  410   b  from the favorites state  408   b  to the page F 1  state  408   f , whereas the cell  530   b  indicates the cost associated with a transition  410   e  from the page F 1  state  408   f  back to the favorites state  408   b.    
     In the depicted example, positive costs are associated with desirable state transitions (e.g., state transitions that are less likely to lead to cycles), whereas negative costs are associated with undesirable state transitions (e.g., state transitions that are more likely to lead to cycles). Thus, the cell  530   a  corresponding to a transition  410   b  from the favorites state  408   b  to the page F 1  state  408   f  is associated with a positive value (e.g., +1), because this transition  410   b  represents forward progress through the user interface  102  and does not seem likely to lead to a cycle. In contrast, the cell  530   b  corresponding to a transition  410   e  from the page F 1  state  408   f  back to the favorites state  408   b  is associated with a negative value (e.g., −1) because this transition  410   e  represents a path that the testing program  112  has already explored and could lead to a cycle (e.g., a cycle that involves alternating between the favorites state  408   b  and the page F 1  state  408   f ). Similarly, the cell  530   g  corresponding to a transition  410   g  from the favorites state  408   b  back to the home state  408   a  is also associated with a negative value. 
     As indicated above, the cost matrix  528  may be used to maintain tallies indicating total costs incurred during a particular test. Suppose that a test begins with the path that is shown in  FIG. 4  and that was discussed above (i.e., home state  408   a →favorites state  408   b →page F 1  state  408   f →page F 2  state  408   g ).  FIGS. 5B-5F  illustrate portions of the cost matrix  528  at various points in time as this path is explored. 
     In particular,  FIG. 5B  illustrates how the cost matrix  528  may be updated after the transition  410   a  from the home state  408   a  to the favorites state  408   b . When this transition  410   a  is made, the cell  532   a  corresponding to this transition  410   a  may be updated with the value from the corresponding cell  530   c  in the adjacency matrix  526 , namely +1. The sum of all of the cells in the cost matrix  528  at this point is +1. 
       FIG. 5C  illustrates how the cost matrix  528  may be updated after the transition  410   b  from the favorites state  408   b  to the page F 1  state  408   f . When this transition  410   b  is made, the cell  532   b  corresponding to this transition  410   b  may be updated with the value from the corresponding cell  530   a  in the adjacency matrix  526 , namely +1. The sum of all of the cells in the cost matrix  528  at this point is +2. 
       FIG. 5D  illustrates how the cost matrix  528  may be updated after the transition  410   c  from the page F 1  state  408   f  to the page F 2  state  408   g . When this transition  410   c  is made, the cell  532   c  corresponding to this transition  410   c  may be updated with the value from the corresponding cell  530   d  in the adjacency matrix  526 , namely +1. The sum of all of the cells in the cost matrix  528  at this point is +3. 
     In the page F 2  state  408   g , there are two possible paths that may be selected. The testing program  112  could activate the link  222   i  to the home page  220   a , thereby causing a transition  410   f  to the home state  408   a . Alternatively, the testing program  112  could activate the link  222   h  to page F 3   220   h , thereby causing a transition  410   d  to the page F 3  state  408   h . To choose between these paths, the testing program  112  may compare what the total value of the cost matrix  528  would be in both scenarios. More specifically, the testing program  112  may determine (i) the total value of the cost matrix  528  that would result from transitioning  410   f  to the home state  408   a , and (ii) the total value of the cost matrix  528  that would result from transitioning  410   d  to the page F 3  state  408   h . The testing program  112  may then compare (i) and (ii) to make a decision about which transition to make. 
       FIG. 5E  illustrates the total value of the cost matrix  528  that would result from transitioning  410   f  from the page F 2  state  408   g  to the home state  408   a . If this transition  410   f  were made, the cell  532   d  corresponding to this transition  410   f  may be updated with the value from the corresponding cell  530   e  in the adjacency matrix  526 , namely −1. The sum of all of the cells in the cost matrix  528  at this point would be +2. 
       FIG. 5F  illustrates the total value of the cost matrix  528  that would result from transitioning  410   d  from the page F 2  state  408   g  to the page F 3  state  408   h . If this transition  410   d  were made, the cell  532   e  corresponding to this transition  410   d  may be updated with the value from the corresponding cell  530   f  in the adjacency matrix  526 , namely +1. The sum of all of the cells in the cost matrix  528  at this point would be +4. 
     At any given point in a user interface  102 , there are typically multiple paths from which to choose. When the testing program  112  is testing a part of the user interface  102  that is beyond the critical depth  324  and there are multiple paths from which to choose, the testing program  112  may make a probability-based selection of a path based on a relative comparison of the total value of the cost matrix  528 . The probability of choosing a particular transition may be expressed as the total value of the cost matrix  528  that would result from that transition divided by the sum of the total value of the cost matrix  528  in all possible scenarios. In the present example, the total value of the cost matrix  528  that would result from transitioning  410   f  from the page F 2  state  408   g  to the home state  408   a  is +2 (as shown in  FIG. 5E ). The total value of the cost matrix  528  that would result from transitioning  410   d  from the page F 2  state  408   g  to the page F 3  state  408   h  is +4 (as shown in  FIG. 5F ). The sum of the total value of the cost matrix  528  in all possible scenarios is therefore 2+4=6. Accordingly, in this example the testing program  112  may be configured so that there is a probability of 2/6 that the transition  410   f  from the page F 2  state  408   g  to the home state  408   a  will be selected, and a probability of 4/6 that the transition  410   d  from the page F 2  state  408   g  to the page F 3  state  408   h  will be selected. Thus, in this example, it is more likely that the testing program  112  chooses to transition  410   d  from the page F 2  state  408   g  to the page F 3  state  408   h , but it is still possible that the testing program  112  may choose to transition  410   f  from the page F 2  state  408   g  to the home state  408   a.    
     In the example just described, when the testing program  112  is in the page F 2  state  408   g , there are two paths from which the testing program  112  can choose: a first path that involves transitioning to the home state  408   a , or a second path that involves transitioning to the page F 3  state  408   h . The testing program  112  may choose between these possible paths by comparing the total cost (e.g., the sum of the total value of the cost matrix  528 ) associated with both paths. The total cost associated with a redundant path may be less favorable than the total cost associated with a new path. In this context, the term “redundant path” may refer to a path that involves transitioning to a state that has previously been explored. In the example just described, the path that involves transitioning from the page F 2  state  408   g  to the home state  408   a  may be considered to be a redundant path. The term “new path” may refer to a path that involves transitioning to a state that has not previously been explored. In the example just described, the path that involves transitioning from the page F 2  state  408   g  to the page F 3  state  408   h  may be considered to be a new path. The total cost associated with the redundant path (transitioning from the page F 2  state  408   g  to the home state  408   a ) is +2 in this example. This value is less favorable than the total cost associated with the new path (transitioning from the page F 2  state  408   g  to the page F 3  state  408   h ), which is +4 in this example. 
     Stated another way, in the present example the testing program  112  selects a next state based at least in part on which of the plurality of possible next states (i.e., which of the home state  408   a  or the page F 3  state  408   h ) would provide a most favorable cost metric. In this context, the term “cost metric” refers to an indication (e.g., a numerical indication) of the relative desirability of particular state transitions. In this example, the cost metric is the total value of the cost matrix  528 . In alternative implementations, a different cost metric may be utilized. 
     In some implementations, when selecting a next state in a scenario where there are a plurality of possible next states and a plurality of possible state transitions, the testing program  112  may select the next state based at least in part on one or more cost metrics associated with the plurality of possible next states and the plurality of possible state transitions. The cost metrics may indicate the relative desirability of possible state transitions. In the example just described, the cost metric (e.g., total value of the cost matrix  528 ) associated with the transition from the page F 2  state  408   g  to the home state  408   a  and the cost metric associated with the transition from the page F 2  state  408   g  to the page F 3  state  408   h  indicate the relative desirability of these state transitions. The cost metrics associated with untested states and untested state transitions may be more favorable than the cost metrics associated with previously tested states and previously tested state transitions. In the example described previously, the transition  410   g  from the favorites state  408   b  back to the home state  408   a  may be considered to be a previously tested state transition, and the home state  408   a  may be considered to be a previously tested state. On the other hand, the transition  410   d  from the page F 2  state  408   g  to the page F 3  state  408   h  may be considered to be a previously untested state transition, and the page F 3  state  408   h  may be considered to be a previously untested state. 
     Referring again to  FIG. 2 , another aspect of the present disclosure is related to the application of testing limits to different sections  234   a - d  of the user interface  102 . For example, one or more testing limits may be applied to the section  234   a  of the user interface  102  that includes the favorites page  220   b  and other associated pages  220   f - h ,  220   l . Similar limits may be applied to other sections  234   b - d . The testing program  112  may be configured to test the links and other elements in the pages within a particular section  234   a - d  until a relevant testing limit is reached. 
     In some implementations, a testing limit may be implemented as a limitation on the amount of time that may be spent testing a particular section  234   a - d . In other words, the testing program  112  may test the links and other elements in the pages within a particular section  234   a - d  until a certain amount of time has elapsed. In some implementations, a testing limit may be implemented as a limitation on the number of transitions that may be made while testing a particular section  234   a - d . In other words, the testing program  112  may test the links and other elements in the pages within a particular section  234   a - d  until a certain number of transitions have been made. 
     More than one testing limit may be applied to a particular section  234   a - d . For example, the testing program  112  may be configured to test the links and other elements in the pages within a particular section  234   a - d  until a time limit or a limit on the number of transitions has been reached, whichever comes first. 
     Another aspect of the present disclosure is related to the scenario in which the current state is within the critical depth  324  and the testing program  112  is choosing between multiple possibilities that are beyond the critical depth  324  for the next state. An example will be discussed in connection with the pages  220  of the user interface  102  that are shown in  FIG. 2  and the corresponding FSM representation that is shown in  FIG. 3 . Suppose that the testing program  112  has navigated to the news state  308   e , which is within the critical depth  324 . There are three different possibilities for the next state: the page N 1  state  308   i , the page N 2  state  308   j , or the page N 3  state  308   k . All of these states  308   i - k  are beyond the critical depth  324 . 
     In this situation, the testing program  112  may be configured to randomly choose one of the possible next states. In other words, in the present example, the testing program  112  may be configured to randomly choose between the page N 1  state  308   i , the page N 2  state  308   j , or the page N 3  state  308   k . From that point forward within that section  234   d  of the user interface  102 , the selection of the next state may be based on probabilities in the manner discussed above. 
     Reference is now made to  FIG. 6 . In some implementations, the testing of the user interface  102  may be distributed across multiple computer systems  636   a - n . For example, different sections  234   a - d  of the user interface  102  may be tested by different computer systems  636   a - n . A controller node  638   n  may be responsible for designing the overall testing strategy. The controller node  638   n  may assign responsibility for testing different sections  234   a - d  of the user interface  102  to different computer systems  636   a - n . These computer systems  636   a - n  may test their assigned section(s)  234   a - d  of the user interface  102  and report the results of the testing (e.g., in the form of one or more logs  118 ) back to the controller node  638 . 
       FIG. 7  illustrates an example of a method  700  for testing a user interface  102  of an application  104  in accordance with the present disclosure. The method  700  includes determining  702  states  108  and state transitions  110  associated with the user interface  102 . This may involve creating an FSM representation of the user interface  102  (an example of which is shown in  FIG. 3 ). 
     Some of the states  108  and state transitions  110  may be tested systematically, while other states  108  and state transitions  110  may be selectively tested. In other words, the method  700  may include exploring  704  all of a first plurality of states  108  and state transitions  110  (i.e., those states  108  and state transitions  110  that are of greatest importance and should be tested systematically) and exploring  706  a subset of a second plurality of states  108  and state transitions  110  (i.e., those states  108  and state transitions  110  that are of lesser importance and may therefore be selectively tested). In some implementations, those states  108  and state transitions  110  that are within a critical depth  324  may be tested systematically, while those states  108  and state transitions  110  that are beyond the critical depth  324  may be selectively tested. 
     As part of exploring  706  the subset of the states  108  and state transitions  110  that can be selectively tested, the method  700  may penalize  708  paths that lead to cycles. This may involve using one or more data structures  114  that define costs associated with particular state transitions  110  and that maintain tallies indicating the total cost that has been incurred during particular tests. State transitions  110  may be selected in a probabilistic manner based on the associated costs. 
       FIG. 8  illustrates certain components that may be included within a computer system  800 . One or more computer systems  800  may be used to implement the various devices, components, and systems described herein. 
     The computer system  800  includes a processor  801 . The processor  801  may be a general purpose single- or multi-chip microprocessor (e.g., an Advanced RISC (Reduced Instruction Set Computer) Machine (ARM)), a special purpose microprocessor (e.g., a digital signal processor (DSP)), a microcontroller, a programmable gate array, etc. The processor  801  may be referred to as a central processing unit (CPU). Although just a single processor  801  is shown in the computer system  800  of  FIG. 8 , in an alternative configuration, a combination of processors (e.g., an ARM and DSP) could be used. 
     The computer system  800  also includes memory  803  in electronic communication with the processor  801 . The memory  803  may be any electronic component capable of storing electronic information. For example, the memory  803  may be embodied as random access memory (RAM), read-only memory (ROM), magnetic disk storage media, optical storage media, flash memory devices in RAM, on-board memory included with the processor, erasable programmable read-only memory (EPROM), electrically erasable programmable read-only memory (EEPROM) memory, registers, and so forth, including combinations thereof. 
     Instructions  805  and data  807  may be stored in the memory  803 . The instructions  805  may be executable by the processor  801  to implement some or all of the functionality disclosed herein, including the method  700  shown in  FIG. 7 . Executing the instructions  805  may involve the use of the data  807  that is stored in the memory  803 . Any of the various examples of modules and components described herein may be implemented, partially or wholly, as instructions  805  stored in memory  803  and executed by the processor  801 . Any of the various examples of data described herein may be among the data  807  that is stored in memory  803  and used during execution of the instructions  805  by the processor  801 . 
     A computer system  800  may also include one or more communication interfaces  809  for communicating with other electronic devices. The communication interface(s)  809  may be based on wired communication technology, wireless communication technology, or both. Some examples of communication interfaces  809  include a Universal Serial Bus (USB), an Ethernet adapter, a wireless adapter that operates in accordance with an Institute of Electrical and Electronics Engineers (IEEE) 802.11 wireless communication protocol, a Bluetooth® wireless communication adapter, and an infrared (IR) communication port. 
     A computer system  800  may also include one or more input devices  811  and one or more output devices  813 . Some examples of input devices  811  include a keyboard, mouse, microphone, remote control device, button, joystick, trackball, touchpad, and lightpen. Some examples of output devices  813  include a speaker and a printer. One specific type of output device that is typically included in a computer system  800  is a display device  815 . Display devices  815  used with embodiments disclosed herein may utilize any suitable image projection technology, such as liquid crystal display (LCD), light-emitting diode (LED), gas plasma, electroluminescence, or the like. A display controller  817  may also be provided, for converting data  807  stored in the memory  803  into text, graphics, and/or moving images (as appropriate) shown on the display device  815 . 
     The various components of the computer system  800  may be coupled together by one or more buses, which may include a power bus, a control signal bus, a status signal bus, a data bus, etc. For the sake of clarity, the various buses are illustrated in  FIG. 8  as a bus system  819 . 
     In accordance with an aspect of the present disclosure, a method for testing a user interface is disclosed. The method may include determining states and state transitions associated with the user interface, exploring a first plurality of states and a first plurality of state transitions of the user interface, exploring a subset of a second plurality of states and a second plurality of state transitions of the user interface, and penalizing paths that lead to cycles within the subset of the second plurality of states and the second plurality of state transitions. 
     The method may further include determining a critical depth for testing the user interface. The first plurality of states and the first plurality of state transitions may be within the critical depth. The second plurality of states and the second plurality of state transitions may be beyond the critical depth. 
     Penalizing the paths within the subset of the second plurality of states and the second plurality of state transitions that lead to cycles may include navigating to a current state of the user interface that is beyond the critical depth and selecting a next state based at least in part on probabilities associated with transitions from the current state to the plurality of possible next states. The user interface may permit navigation from the current state to a plurality of possible next states. A probability associated with a transition from the current state to a possible next state may be associated with a likelihood that the transition leads to a cycle. 
     Penalizing the paths within the subset of the second plurality of states and the second plurality of state transitions that lead to cycles may include navigating to a current state of the user interface that is beyond the critical depth and selecting a next state based at least in part on which of the plurality of possible next states would provide a most favorable cost metric. The user interface may permit navigation from the current state to a plurality of possible next states. 
     Penalizing the paths within the subset of the second plurality of states and the second plurality of state transitions that lead to cycles may include providing a first data structure that defines costs associated with transitioning between different states of the user interface, providing a second data structure that maintains tallies indicating a total cost incurred during a test, and using information from the first data structure to update the second data structure in connection with exploring the subset of the second plurality of states. 
     The method may further include determining testing limits for different sections of the user interface. 
     The method may further include navigating to a current state of the user interface that is within a critical depth and randomly selecting one of the plurality of possible next states as a next state. The user interface may permit navigation from the current state to a plurality of possible next states that are beyond the critical depth. 
     The testing of the user interface may be distributed across multiple computer systems. 
     In accordance with another aspect of the present disclosure, a system for testing a user interface is disclosed. The system may include one or more processors, memory in electronic communication with the one or more processors, and instructions stored in the memory. The instructions may be executable by the one or more processors to determine states and state transitions associated with the user interface, explore a first plurality of states and a first plurality of state transitions of the user interface, explore a subset of a second plurality of states and a second plurality of state transitions of the user interface, and penalize paths within the subset of the second plurality of states and the second plurality of state transitions that lead to cycles. 
     The instructions may also be executable by the one or more processors to determine a critical depth for testing the user interface. The first plurality of states and the first plurality of state transitions may be within the critical depth. The second plurality of states and the second plurality of state transitions may be beyond the critical depth. 
     Penalizing the paths within the subset of the second plurality of states and the second plurality of state transitions that lead to cycles may include navigating to a current state of the user interface that is beyond the critical depth and selecting a next state based at least in part on probabilities associated with transitions from the current state to the plurality of possible next states. The user interface may permit navigation from the current state to a plurality of possible next states. A probability associated with a transition from the current state to a possible next state may be associated with a likelihood that the transition leads to a cycle. 
     Penalizing the paths within the subset of the second plurality of states and the second plurality of state transitions that lead to cycles may include navigating to a current state of the user interface that is beyond the critical depth and selecting a next state based at least in part on cost metrics associated with the second plurality of states and the second plurality of state transitions. The user interface may permit navigation from the current state to a plurality of possible next states. The cost metrics may indicate relative desirability of possible state transitions. The cost metrics associated with untested states and untested state transitions may be more favorable than the cost metrics associated with previously tested states and previously tested state transitions. 
     Penalizing the paths within the subset of the second plurality of states and the second plurality of state transitions that lead to cycles may include providing a first data structure that defines costs associated with transitioning between different states of the user interface, providing a second data structure that maintains tallies indicating a total cost incurred during a test, using information from the first data structure to update the second data structure in connection with exploring the subset of the second plurality of states, and choosing between a plurality of possible paths by comparing the total cost associated with each of the plurality of possible paths. The total cost associated with a redundant path may be less favorable than the total cost associated with a new path. 
     The instructions may also be executable by the one or more processors to determine testing limits for different sections of the user interface. 
     The instructions may also be executable by the one or more processors to navigate to a current state of the user interface that is within a critical depth and randomly select one of the plurality of possible next states as a next state. The user interface may permit navigation from the current state to a plurality of possible next states that are beyond the critical depth. 
     In accordance with another aspect of the present disclosure, a method for testing a user interface may include determining a critical depth for testing the user interface, exploring all of a first plurality of states and a first plurality of state transitions that are within the critical depth, exploring a subset of a second plurality of states and a second plurality of state transitions that are beyond the critical depth, and penalizing some of the second plurality of state transitions that lead to redundant paths. 
     The first plurality of states and the first plurality of state transitions may be within the critical depth. The second plurality of states and the second plurality of state transitions may be beyond the critical depth. 
     Penalizing some of the second plurality of state transitions that lead to redundant paths may include navigating to a current state of the user interface that is beyond the critical depth and selecting a next state based at least in part on which of the plurality of possible next states would provide a most favorable cost metric. The user interface may permit navigation from the current state to a plurality of possible next states. 
     Penalizing some of the second plurality of state transitions that lead to redundant paths may include providing a first data structure that defines costs associated with transitioning between different states of the user interface, providing a second data structure that maintains tallies indicating a total cost incurred during a test, and using information from the first data structure to update the second data structure in connection with exploring the subset of the second plurality of states. 
     The method may further include navigating to a current state of the user interface that is within the critical depth and randomly selecting one of the plurality of possible next states as a next state. The user interface may permit navigation from the current state to a plurality of possible next states that are beyond the critical depth. 
     The techniques described herein may be implemented in hardware, software, firmware, or any combination thereof, unless specifically described as being implemented in a specific manner. Any features described as modules, components, or the like may also be implemented together in an integrated logic device or separately as discrete but interoperable logic devices. If implemented in software, the techniques may be realized at least in part by a non-transitory processor-readable storage medium comprising instructions that, when executed by at least one processor, perform one or more of the methods described herein. The instructions may be organized into routines, programs, objects, components, data structures, etc., which may perform particular tasks and/or implement particular data types, and which may be combined or distributed as desired in various embodiments. 
     The steps and/or actions of the methods described herein may be interchanged with one another without departing from the scope of the claims. In other words, unless a specific order of steps or actions is required for proper operation of the method that is being described, the order and/or use of specific steps and/or actions may be modified without departing from the scope of the claims. 
     The term “determining” encompasses a wide variety of actions and, therefore, “determining” can include calculating, computing, processing, deriving, investigating, looking up (e.g., looking up in a table, a database or another data structure), ascertaining and the like. Also, “determining” can include receiving (e.g., receiving information), accessing (e.g., accessing data in a memory) and the like. Also, “determining” can include resolving, selecting, choosing, establishing and the like. 
     The terms “comprising,” “including,” and “having” are intended to be inclusive and mean that there may be additional elements other than the listed elements. Additionally, it should be understood that references to “one embodiment” or “an embodiment” of the present disclosure are not intended to be interpreted as excluding the existence of additional embodiments that also incorporate the recited features. For example, any element or feature described in relation to an embodiment herein may be combinable with any element or feature of any other embodiment described herein, where compatible. 
     The present disclosure may be embodied in other specific forms without departing from its spirit or characteristics. The described embodiments are to be considered as illustrative and not restrictive. The scope of the disclosure is, therefore, indicated by the appended claims rather than by the foregoing description. Changes that come within the meaning and range of equivalency of the claims are to be embraced within their scope.