Patent Publication Number: US-6907550-B2

Title: Stochastic simulation of computer activity based on user categories

Description:
BACKGROUND OF THE INVENTION 
     1. The Field of the Invention 
     The present invention relates to the automated testing of computer systems. More specifically, the present invention relates to methods, systems, and computer program products for stochastically measuring the reliability of a computer system based on the expected usage by a variety of different users. 
     2. Background and Related Art 
     Computing systems are available in a wide-variety of forms including desktop computers and laptop computers. Even hand-held devices such as Personal Digital Assistants (PDAs) and cellular telephones have significant general-purpose processing and memory capabilities, especially when viewed from a historical perspective. Such hand-held devices may even run sophisticated operating systems that allow for the simultaneous usage of multiple software applications. 
     Current operating systems and supported applications can be quite complex. In order to operate properly, each application must interact harmoniously with the operating system (and with potentially other applications) so that the computer system functions as planned. It is often impractical to expect that a first pass at coding and compiling an application will result in a perfect finished product. Even a seemingly minor programming error may introduce significant performance deviations. With typical software applications often being compiled from many thousands of lines of code, one can appreciate that even the most experienced programmer will not catch every programming error in an application in the first instance. Accordingly, computer system and software providers extensively test their product to be sure the computer system works as intended. 
     One conventional approach to measuring software reliability is to send a partially complete software product out to a large population of users to test the product. However, it is often expensive to create a software product (even one with partial functionality) and distribute it to a large number of users. Additionally, sending such a partially complete software product may inadvertently allow competitors an advanced view of a product thereby reducing the product&#39;s competitive advantage. 
     Another conventional approach to measuring computer system reliability is to internally hire and train skilled testers to systematically exercise the system to find bugs. However, this approach to testing is highly labor intensive, and thus can be time consuming and expensive. Also, the skilled testers may not run the system through the same sequence of actions that a typical user might. Accordingly, some defects in the system may go unnoticed until the system is actually in the possession of the end-user. 
     In another conventional testing approach, computer-executable script is drafted that causes the system to perform a series of particular actions. While this approach does not necessarily require skilled testers to systematically exercise the system, the actions caused by executing the script will not necessarily approximate how an actual end-user might use the system. 
     Even if a software test accurately simulates how an actual user may use a system, there are many different types of users. For example, consider a system in the form of a PDA running phone, email, and Web navigation software. A regular consumer may use the phone software most frequently, with the email and Web navigation software being used less frequently. However, a traveling businessperson may use the email software most frequently, while using the phone a little less, and using the Web navigation software least of all. Accordingly, different user segments may use a system in dramatically different ways. Thus, even if a technique accurately tests a given user&#39;s use of the system, the technique may not be accurate for all users of the system. 
     Accordingly, what is desired are methods, systems, and computer program products for more realistically simulating system performance. 
     BRIEF SUMMARY OF THE INVENTION 
     The principles of the present invention provide for testing a computer system by simulating the computer system activity that would occur as it experiences a projected use pattern. The computer system may accomplish this for a number of projected use patterns. For example, suppose that a particular computer system is quite general purpose so as to be attractive to multiple market segments (e.g., students, leisure travelers, business persons, gamers, or the like). Some of these market segments may use the computer system predominantly for making telephone calls, with only some attention to email or Web access. Other market segments may be more interested in email, and less at Web access. 
     Different use patterns will sometimes give rise to different failure mechanisms. Accordingly, if one single use pattern is used to simulate user activity, one might overlook a number of failure mechanisms that might have been fixed if detected. The present invention allows for testing using a wide variety of projected use patterns thereby increasing the chance that faults in the computer system will be detected and corrected prior to marketing the product. 
     The present invention may accomplish this by navigating through a decision tree. Each of the use patterns may perform a number of standard functions that are inherent to the computer system. For example, such standard functions may include a phone, email, and web function in the case of a Personal Digital Assistant (PDA) or Internet-enabled mobile telephone. For each of the projected use patterns, weights are assigned to each of the standard functions. The weights represent the chance that a test from a particular standard function will be performed given a particular projected use pattern. 
     A standard function is then selected based on the weight assigned to the standard function given the projected use pattern. Then, a probability tree is navigated to determine a particular test to implement. For example, in the case of a phone standard function, available tests might include calling directly from a contacts list, calling by dialing numbers, dialing a busy line, or other phone-base activities. 
     Accordingly, by navigating the decision tree for a number of project use patterns, the system may be tested for a wider range of users. In this way, defects that would have normally occurred during a wide range of usage patterns will be more likely detected and corrected instead of being discovered by the end-user. 
     Additional features and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by the practice of the invention. The features and advantages of the invention may be realized and obtained by means of the instruments and combinations particularly pointed out in the appended claims. These and other features of the present invention will become more fully apparent from the following description and appended claims, or may be learned by the practice of the invention as set forth hereinafter. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       In order to describe the manner in which the above-recited and other advantages and features of the invention can be obtained, a more particular description of the invention briefly described above will be rendered by reference to specific embodiments thereof which are illustrated in the appended drawings. Understanding that these drawings depict only typical embodiments of the invention and are not therefore to be considered to be limiting of its scope, the invention will be described and explained with additional specificity and detail through the use of the accompanying drawings in which: 
         FIG. 1  represents a computer system in the form of a mobile computing device that represents a suitable operating environment for the present invention; 
         FIG. 2  schematically illustrates a decision tree that may be navigated in order to test the computer system for a number of different project use patterns; 
         FIG. 3  illustrates a flowchart of a method for testing a computer system that has a number of project use patterns; 
         FIG. 4  schematically illustrates a decision tree with redundant nodes merged; and 
         FIG. 5  illustrates a data structure that may be used to generate the decision tree of FIG.  2 . 
     
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     The principles of the present invention provide for testing a computer system by simulating the computer system activity that would occur as it experiences a projected use pattern. The computer system may accomplish this for a number of projected use patterns. Different use patterns will sometimes give rise to different failure mechanisms. Accordingly, if one single use pattern is used to simulate user activity, one might overlook a number of failure mechanisms that might have been fixed if detected. The present invention allows for testing using a wide variety of projected use patterns. 
     The present invention may accomplish this by navigating through a decision tree. Each of the use patterns may perform a number of standard functions (e.g., phone, email, Web, or the like) that are inherent to the computer system. For each of the projected use patterns, weights are assigned to each of the standard functions. A standard function is then selected based on the weight assigned to the standard function given the projected use pattern. Then, a probability tree is navigated to determine a particular test to implement. 
     The embodiments of the present invention may comprise a special purpose or general purpose computing device including various computer hardware, as discussed in greater detail below. Embodiments within the scope of the present invention also include computer-readable media for carrying or having computer-executable instructions or data structures stored thereon. Such computer-readable media can be any available media, which can be accessed by a general purpose or special purpose computer. By way of example, and not limitation, such computer-readable media can comprise physical storage media such as RAM, ROM, EEPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to carry or store desired program code means in the form of computer-executable instructions or data structures and which can be accessed by a general purpose or special purpose computer. 
     When information is transferred or provided over a network or another communications connection (either hardwired, wireless, or a combination of hardwired or wireless) to a computer, the computer properly views the connection as a computer-readable medium. Thus, any such connection is properly termed a computer-readable medium. Combinations of the above should also be included within the scope of computer-readable media. Computer-executable instructions comprise, for example, instructions and data which cause a general purpose computer, special purpose computer, or special purpose processing device to perform a certain function or group of functions. 
     Although not required, the invention will be described in the general context of computer-executable instructions, such as program modules, being executed by computing devices. Generally, program modules include routines, programs, objects, components, data structures, and the like that perform particular tasks or implement particular abstract data types. 
     Those skilled in the art will appreciate that the invention may be practiced in network computing environments with many types of computer system configurations, including personal computers, hand-held devices, multi-processor systems, microprocessor-based or programmable consumer electronics, network PCs, minicomputers, mainframe computers, and the like. The invention may also be practiced in distributed computing environments where tasks are performed by local and remote processing devices that are linked (either by hardwired links, wireless links, or by a combination of hardwired or wireless links) through a communications network. In a distributed computing environment, program modules may be located in both local and remote memory storage devices. 
       FIG. 1  illustrates a computing system  100  that includes a user interface  101  for allowing a user to input information through an input user interface  103 , and review information presented via an output user interface  102 . For example, the output user interface  102  includes a speaker  104  for presenting audio information to the user, as well as a display  105  for presenting visual information to the user. The computing system  100  also has an antenna  109  for wireless communication over a wireless link. 
     The input user interface  103  may include a microphone  106  for rendering audio information into electronic form. In addition, the input user interface  103  includes dialing controls  107  represented by  12  buttons through which a user may dial a telephone number, enter a text message, or instruct the computing system  100  to send a data message. Input user interface  103  also includes navigation control buttons  108  that assist the user in navigating through various entries and options that may be listed on display  105 . 
     Although the computing system  100  has the appearance of a mobile telephone, the unseen features of the computing system  100  may allow for complex and flexible general-purpose processing capabilities. For example, the computing system  100  also includes a processor  111  and a memory  112  that are connected to each other and to the user interface  101  via a bus  110 . The memory  112  generically represents a wide variety of volatile and/or non-volatile memories that may be employed. The particular type of memory used in the computing system  100  is not important to the present invention. 
     Program code means comprising one or more program modules may be stored in memory  112 . The one of more program modules may include an operating system  113 , one or more application programs  114 , other program modules  115 , and program data  116 . The environment illustrated in  FIG. 1  is illustrative only, and by no means represents even a small portion of the wide variety of computing devices in which the principles of the present invention may be implemented. 
     For example, although the computing system  100  is illustrated as being a mobile telephone, any at least partially general-purpose processing system may employ the principles of the present invention. For example, Personal Digital Assistants (PDAs), laptop desktop computers, and computer networks may perform the methods described herein. 
       FIG. 2  illustrates a decision tree  200  that the computer system  100  may navigate in order to test the interoperability of the various modules that run on the computer system  100  such as, for example, the operating system  113 , the application programs  114 , or the program modules  115 . The navigation of the decision tree  200  will be described with frequent reference to  FIG. 3 , which illustrates a flowchart of a method  300  for testing a computer system that has a number of projected use patterns. 
     The decision tree  200  includes a starting point  201  where the navigation begins. It may be anticipated that the computing system  100  is going to be used by a wide variety of users having a wide variety of needs. Accordingly, the computing system  100  can be expected to experience a variety of projected use patterns. In  FIG. 2 , the projected use patterns  210  are represented by triangular nodes in the decision tree  200 . In the illustrated example, such projected use patterns include an “Average User” use pattern  211 , a “Heavy Phone” use pattern  212 , a “Heavy Email” use pattern  213 , and a “Heavy Web” use pattern  214 . 
     The different use patterns may have been determined based on information as extensive as marketing surveys, or even information such as a simple educated guess on how a particular computer system will be used. It is possible, or even likely, that projected use patterns may differ depending on the nature of the computer system. The example projected use patterns may be suitable for a PDA with phone and Internet access capabilities, or a mobile phone with Internet access capabilities, although the present invention is not so limited. The decision tree  200  includes horizontal ellipses  215  that represent other projected use patterns thereby emphasizing that the principles of the present invention are by no means limited to the illustrated projected use patterns. 
     For each projected use pattern, there are a number of standard functions  220  that may be performed. Each standard function  220  is represented by a circular node in the decision tree  200 . For example, the “Average User” projected use pattern  211  has a “Phone” standard function  221 A, an “Email” standard function  221 B and a “Web” standard function  221 C, among potentially other as represented by horizontal ellipses  211 D. The standard functions represent high-level functional operations whose usage may vary across different projected use patterns. 
     Since the testing occurs on a given computer system, the standard functions may often be the same across all of the projected use patterns. Accordingly, the principles of the present invention are described with the standard functions being the same across all of the projected use patterns, although the invention is not so limited. For example, Heavy Phone projected use pattern  212  also includes a Phone standard function  222 A, an Email standard function  222 B and a Web standard function  222 C, among others  222 D. Likewise, Heavy Email projected use pattern  213  includes a Phone standard function  223 A, an Email standard function  223 B and a Web standard function  223 C, among others  223 D. Also, Heavy Web projected use pattern  214  includes a Phone standard function  224 A, an Email standard function  224 B and a Web standard function  224 C, among others  224 D. 
     Each of the standard functions may have a number of possible tests that may be performed once the test navigates to the standard function. The test that is actually performed may be determined from a probability tree. The decision tree  200  includes a number of probability trees  230  including a phone probability tree  231 A for the phone standard function  221 A, an Email probability tree  231 B for the Email standard function  221 B, and a Calendar probability tree  231 C for the Calendar standard function  221 C. For clarity, the other probability trees corresponding to the standard functions for the “Heavy Phone” projected use pattern  212 , the “Heavy Email” projected use pattern  213 , and the “Heavy Web” projected use pattern  214  are not shown. 
     The structure of the probability tree may be sophisticated including a number of hierarchical nodes and branches, or may be relatively straightforward as is illustrated for probability tree  231 A. The probability tree  231 A includes a “Call From Contacts” test  231 AA, “Push Button Call” test  231 AB, a “Call Busy Line” test  231 AC, among others  231 AD. The tests are the terminating nodes in the decision tree  200  and are represented as square nodes. The tests may be any form of computer-executable code including scripts, such as an executable file or a script file. 
       FIG. 3  illustrates a flowchart of a method  300  for testing the computer system  100 . The method  300  includes an act of representing weights for the standard functions for each of the plurality of use patterns (act  310 ). For example, referring the Average User projected use pattern  211  in  FIG. 2 , the standard functions  221 A,  221 B,  221 C, and  221 D have corresponding weights 40%, 25%, 25%, and 10%, respectively. This means that when the Average User projected use pattern  211  is selected, 40% of the tests performed during the simulation will be from the Phone standard function  221 A, 25% from the Email standard function  221 B, 25% from the Web standard function  221 C, and 10% from the other standard functions  221 D. Likewise, the Heavy Phone projected use pattern  212  has respective weights 70%, 10%, 10% and 10% indicating heavy emphasis on tests from the Phone standard function  222 A. Also, the Heavy Email projected use pattern  213  has respective weights 6%, 44%, 44% and 6% indicating heavy emphasis on tests from the Email standard function  223 B and Web standard function  223 C. Finally, the Heavy Web projected use pattern  214  has respective weights 9%, 9%, 73% and 9% indicating heavy emphasis on tests from the Web standard function  224 C. 
     Referring to  FIG. 3 , one of the projected use patterns is then selected (act  320 ). The computing system  100  may make this selection after having received a specific user instruction, in response to a preprogrammed instruction, or on its own initiative based on decision-making logic. Suppose in this example, that the computing system  100  has selected the Average User projected use pattern  211 . 
     Then, the computing system  100  determines which standard function category to perform (step  330 ) based on the probability weight corresponding to the standard function for the selected projected use pattern. This functional step may be accomplished via any corresponding acts that accomplish the specified function. However, in the illustrated embodiment, this functional step is accomplished via specific corresponding acts  331 ,  332  and  333 . 
     In particular, the computing system  100  may generate an arbitrary value (act  331 ) via, for example, a pseudo random number generator. Next, the arbitrary value (or a value derived therefrom) is compared to the probability weight assigned to the particular standard function (act  332 ). Then, it is determined based on the comparison that the particular standard function is to be performed (act  333 ). For example, suppose that the arbitrary value is a whole number between 1 and 100, inclusive. For the Average User project use pattern  211 , if the number is between 1 and 40, inclusive, a test from the Phone standard function  221 A is performed. If the number is between 40 and 65, inclusive, a test from the Email standard function  221 B is performed. If the number is between 66 and 90, inclusive, a test from the Web standard function  221 C is performed. If the number is between 91 and 100, inclusive, a test from one of the other standard functions  221 D is performed. 
     Suppose that the navigation process travels to the Phone standard function  221  A. The navigation would then proceed through the probability tree  231 A until a test is performed. In this probability tree, a probability weight is assigned to each test. For example, the Call From Contacts test  231 AA has a weight of 10%, the Push Button Call test  231 AB has a weight of 80%, and the Call Busy Line test  231 AC has a weight of 10%. Thus, when the Average User projected use pattern  211  is selected, and the phone standard function  221 A is navigated to, a call will be placed by pushing number buttons 80% of the time, a call will be placed directly from a contacts list selection 10% of the time, and a busy signal will be encountered 10% of the times for a total of 100%. Note that other tests  231 AD do not show a probability, implying a zero probability of occurrence for other tests  231 AD in the projected use pattern, which may be an indication that the probability is unknown, and therefore for purposes of testing is implied to be zero. 
     Not all processes performed by the computing system  100  will be in response to user activity. Some processes will occur regardless of user activity. For example, the user may receive a Short Text Messaging (SMS) message while making a phone call. Such processes are often termed asynchronous since they are not necessarily synchronous with user activity, but may occur at any time. Accordingly, the decision tree  200  also includes asynchronous tests  240  such as tests  241  and  242  that may occur at any point during the simulation. 
     In some instances, the decision tree will be the same for each projected use pattern except for the weights assigned to the standard functions. The probability tree for each standard function as well as the tests available might be the same. In that case, the decision tree of  FIG. 2  may be simplified to merge redundant nodes as illustrated in the decision tree  400  of FIG.  4 . In that case, the nodes previously descendant from the Heavy Phone projected use pattern  212 , the Heavy Email projected use pattern  213  and the Heavy Web projected use pattern  214  are merged with the nodes that descend from the Average User projected use pattern  211 . 
       FIG. 5  illustrates an example data structure  500  that may be used to form the decision tree  200 . The data structure may be, for example, a registry structure having a root of, for example, [HKEY_LOCAL_MACHINE\SOFTWARE\Testing\Switcher]. The example data structure  500  may include, for example, a projected use field  510  that includes a number of projected use patterns fields  511 ,  512 ,  513 , and so forth. Also, the example data structure  500  includes a test field  520  that includes test definitions such as test definition  521 ,  522  and so forth. 
     This structure may be restated as follows: 
     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 Profiles 
               
            
           
           
               
               
            
               
                   
                 &lt;pname-a&gt;=&lt;prob-a-1&gt;,&lt;prob-a-2&gt;,&lt;prob-a-3&gt; . . . 
               
               
                   
                 &lt;pname-b&gt;=&lt;prob-b-1&gt;,&lt;prob-b-2&gt;,&lt;prob-b-3&gt; . . . 
               
               
                   
                 &lt;pname-c&gt;=&lt;prob-c-1&gt;,&lt;prob-c-2&gt;,&lt;prob-c-3&gt; . . . 
               
            
           
           
               
               
            
               
                   
                 . 
               
               
                   
                 . 
               
               
                   
                 . 
               
            
           
           
               
               
            
               
                   
                 Tests 
               
            
           
           
               
               
            
               
                   
                 S1 
               
            
           
           
               
               
            
               
                   
                 &lt;S1-tname-a&gt;=&lt;prob-a&gt;,&lt;cmd-a-1&gt;,&lt;cmd-a-2&gt; . . . 
               
               
                   
                 &lt;S1-tname-b&gt;=&lt;prob-b&gt;,&lt;cmd-b-1&gt;,&lt;cmd-b-2&gt; . . . 
               
               
                   
                 &lt;S1-tname-c&gt;=&lt;prob-c&gt;,&lt;cmd-c-1&gt;,&lt;cmd-c-2&gt; . . . 
               
            
           
           
               
               
            
               
                   
                 . 
               
               
                   
                 . 
               
               
                   
                 . 
               
            
           
           
               
               
            
               
                   
                 S2 
               
            
           
           
               
               
            
               
                   
                 &lt;S2-tname-a&gt;=&lt;prob-a&gt;,&lt;cmd-a-1&gt;,&lt;cmd-a-2&gt; . . . 
               
               
                   
                 &lt;S2-tname-b&gt;=&lt;prob-b&gt;,&lt;cmd-b-1&gt;,&lt;cmd-b-2&gt; . . . 
               
               
                   
                 &lt;S2-tname-c&gt;=&lt;prob-c&gt;,&lt;cmd-c-1&gt;,&lt;cmd-c-2&gt; . . . 
               
            
           
           
               
               
            
               
                   
                 . 
               
               
                   
                 . 
               
               
                   
                 . 
               
            
           
           
               
               
            
               
                   
                 . 
               
               
                   
                 . 
               
               
                   
                 . 
               
               
                   
                   
               
            
           
         
       
     
     In this example structure, &lt;pname-n&gt; is the name of the projected use pattern n, where n is the value of that name. &lt;prob-n-m&gt; is the probability of a standard function m being selected given the projected use pattern n. Sm represents the standard function m. &lt;Sm-tname-p&gt; represents the test name p for the standard function m. &lt;prob-p&gt; represents the probability of selecting the test p given the standard function. &lt;cmd-p-q&gt; represents the q&#39;th command of the test p. 
     The following is a specific example of such registry data structure:
     [HKEY_LOCAL_MACHINE\SOFTWARE\TESTING]   [HKEY_LOCAL_MACHINE\SOFTWARE\TESTING\Switcher]   [HKEY_LOCAL_MACHINE\SOFTWARE\TESTING\Switcher\Profiles]   “Average User”=“40,25,25,10”   “Heavy Phone”=“70,10,10,10”   “Heavy Email”=“10,80,80,10”   “Heavy Web”=“10,10,80,10”   [HKEY_LOCAL_MACHINE\SOFTWARE\TESTING\Switcher\Tests]   [HKEY_LOCAL_MACHINE\SOFTWARE\TESTING\Switcher\Tests\S1]   “Dialer”=“10,sertest switcher_dialer.txt”   “Work”=“20,-mytest setup,sertes work.txt,mytest shutdown”   [HKEY_LOCAL_MACHINE\SOFTWARE\TESTING\Switcher\Tests\S2]   “In Folders”=“10,sertest switcher_inbox_folders.txt”   “In IMAP”=“30, sertest switcher_inbox_imap.txt”   “In Add Sender”=“25,sertest switcher_inbox_addsender.txt”   [HKEY_LOCAL_MACHINE\SOFTWARE\TESTING\Switcher\Tests\S3]   “Pie”=“25,sertest switcher_pit.txt”   “Pie Random”=“30,sertest switcher_pie_random.txt”   [HKEY_LOCAL_MACHINE\SOFTWARE\TESTING\Switcher\Tests\S4]   “Monkey”=“23,cemonkey/r5/d”   “CE MAPI”=“35,cemapi-i 1-t2-r”   “Stress 5”=“2, stress5 0 1 5”   

     In this example, the names of the specific tests (Dialer, Work, In Folders, In IMAP, In Add Sender, Pie, Pie Random, Monkey, CE MAPI, and Stress 5) are arbitrary and may be replaced by any desired test name. 
     Accordingly, the principles of the present invention allows for the testing of a computing system by simulating computing activity that occurs under a wide variety of projected use patterns. Thus, the stability of the computer system is more assured for a more realistic cross section of users. 
     The present invention may be embodied in other specific forms without departing from its spirit or essential characteristics. The described embodiments are to be considered in all respects only as illustrative and not restrictive. The scope of the invention is, therefore, indicated by the appended claims rather than by the foregoing description. All changes, which come within the meaning and range of equivalency of the claims, are to be embraced within their scope.