© 2006 A.W. Krings CS448/548 Survivable Systems and Networks, Sequence 15Usage ModelsThis discussion is based on the paper:–[Whi93] Whittaker James A., and J.H. Poore, Markov Analysis of Software Specifications, ACM Transactions on Software Engineering and Methodology, Vol.2, No.1, January 1993, pp. 93-106.–We will discuss the paper for what it represents and later see how the approach can benefit us with respect to our “mission” The paper discusses Markov Chains as models for software usage –uses finite state discrete parameter Markov chain–states of the Markov chain represent entries from the input domain of the software–transitions (arcs) define ordering that determines the event space, or sequence, of the experiment1© 2006 A.W. Krings CS448/548 Survivable Systems and Networks, Sequence 15Usage ModelsBlack box view of software system[Whi93, fig.1]2© 2006 A.W. Krings CS448/548 Survivable Systems and Networks, Sequence 15Usage ModelsMarkov analysis of software specifications–define underlying probability law for the usage of the software under consideration–analysis of specification done prior to design and coding–analysis yields irreducible Markov chain (usage Markov chain)»unique start state S0»unique final state SF»set of intermediate usage states Si »states set S = {S0,SF} union Si»set S is ordered by probabilistic transition relation »next state is independent of all past states given the present statesMarkov property (first order chain)3© 2006 A.W. Krings CS448/548 Survivable Systems and Networks, Sequence 15Usage ModelsUsage Markov chain has two properties–Structural Phase»the states and transitions of the chain are established–Statistical Phase»the transition probabilities are assignedHighest level transition diagram[Whi93, fig. 2]4© 2006 A.W. Krings CS448/548 Survivable Systems and Networks, Sequence 15Usage ModelsExample: a simple window application [Whi93, fig3]5© 2006 A.W. Krings CS448/548 Survivable Systems and Networks, Sequence 15Usage ModelsExample Software Specification[Whi93, table I]6© 2006 A.W. Krings CS448/548 Survivable Systems and Networks, Sequence 15Usage ModelsExpansion of the top level usage diagram [Whi93, fig, 4]7© 2006 A.W. Krings CS448/548 Survivable Systems and Networks, Sequence 15Usage ModelsStructural phase - Constructing the usage Markov chain–phase is complete when usage is completely modeled[Whi93, fig,5]8© 2006 A.W. Krings CS448/548 Survivable Systems and Networks, Sequence 15Usage ModelsStatistical Phase–assignment of transition probabilities–different approaches to statistical phase»uninformed approachassign uniform probability distribution across the exit arcs for each stateuseful when no information is available to make more informed choice»informed approachwhen some actual user sequences are availablecould be captured inputs from a prototype, or profiling informationresulting relative frequencies can be used to estimate the transition probability in the usage chain»intended approachsimilar to informed approach but...sequences are obtained by hypothesizing runs of the software by a careful and reasonable userrelative frequency estimates of transition probabilities are computed from the symbol transition counts as in the informed approach–How does one rank the approaches?9© 2006 A.W. Krings CS448/548 Survivable Systems and Networks, Sequence 15Usage ModelsCaptured or hypothesized sequences [Whi93, table II]10© 2006 A.W. Krings CS448/548 Survivable Systems and Networks, Sequence 15Usage ModelsAssigning transition probabilities [Whi93, table II]11© 2006 A.W. Krings CS448/548 Survivable Systems and Networks, Sequence 15(putting it on one page)12© 2006 A.W. Krings CS448/548 Survivable Systems and Networks, Sequence 15Usage ModelsTest Cases–Statistical Test Case»any connected state sequence of the usage chain begins in the start state and ends in the termination stateUsage Distribution π –the structure of the usage chain induces a probability distribution on the input domain of the software–this distribution is called usage distribution–each state Si has steady-state probability πi »i.e., the probability of being in state i is πi 13© 2006 A.W. Krings CS448/548 Survivable Systems and Networks, Sequence 15Usage ModelsUsage Distribution π –usage distribution can be computed by–P is the transition matrix of the usage chain»P can be encoded as a 2-D matrix (P is a square matrix)»state labels are indices and transition probabilities are entries»each row sums up to one»each entry πi is the expected appearance rate of state Si in the long run»this tells software testers where the user spends most of its timeperhaps focus attention on these partsthere is a danger to this though, the bug may be in the less used functions»states can be grouped (allows comparison of subsections of software)usage distributions are just summed up collapsing states in a Markov chain may require adjustments to transitions14© 2006 A.W. Krings CS448/548 Survivable Systems and Networks, Sequence 15Usage ModelsOther useful statisticsNumber of states necessary until Si is expected to be visited, denoted by xi–if Si is the termination state, then xi is the expected number of states until termination of the software15© 2006 A.W. Krings CS448/548 Survivable Systems and Networks, Sequence 15Usage ModelsExpected number of sequences si necessary until state i occurs–largest element of vector s identifies the amount of expected testing until all usage states are encountered at least once–note: TERM indicates termination state16© 2006 A.W. Krings CS448/548 Survivable Systems and Networks, Sequence 15Usage ModelsAnalytical results for example usage model[Whi93, table III]17© 2006 A.W. Krings CS448/548 Survivable Systems and Networks, Sequence 15Usage ModelsMean first passage times mjk–mjk is the expected number of usage states visited starting from Sj until the first visit to Sk–pij indicate the transition probabilities–indicates the extent to which Si and Sk are encountered within the same sequence–e.g. if mjk is greater than the expected test case length, then»occurrence of Sj followed by Sk is expected to require multiple sequences–note: in figure of next slide the diagonal is vector x18© 2006 A.W. Krings CS448/548 Survivable Systems and Networks, Sequence