[IGSTK-Developers] State Machine requirements

[Kevin Gary]

David,

I think I understand you perfectly. But my takeaway from the
meeting was "fully populated state transition table", and I did
not recall flagging any transitions as impossible/invalid in some
sense. For safety testing, we must still evaluate all transitions
along all paths, even if they are "No Action" or invalid. Hence
the combinatorics imply intractability. I say the number of
paths can get even higher because I did not consider loop testing,
and most of our tests in fact have loops, as a common pattern is
to be in some post-initialized state, be asked to do something,
do it, then revert back to the posty-initialized (waiting) state.

Despite the bad news on complexity, I am currently thinking that our
analysis/testing tool really only need be concerned with edge testing
(meaning transition testing for us). The goal of path testing is to
ensure that no accumulative "residue" from prior computations has a
negative effect on later computations - yet we will not be testing
the actual computations (private method calls) in our tool, we will
stub these out.

It might be more useful for us to consider only the paths you suggest
in our testing in this way, I will certainly noodle on this...

Thanks,
KG


David Gobbi wrote:
> Hi Kevin,
> 
> I have added a wiki page on State Machine Design Guidelines:
> http://public.kitware.com/IGSTKWIKI/index.php/State_Machine_Design_Guidelines 
> 
> 
> It includes the method naming conventions that were discussed at the 
> meeting.  I promised to put those on the wiki a month ago, and finally, 
> there they are!
> 
> Soon I will add a complete diagram for the Attempt pattern including not 
> only the states and inputs, but the methods and transition-table entries 
> as well, and a couple examples to go along with it.
> 
> Your info about transition tables is interesting.  The number unique 
> paths is actually going to be much lower than that, since most 
> input/state combinations will result in the same "NoAction" or 
> "InvalidRequest" non-transitions as a lot of other input/state 
> combinations.
> 
> Plus there are some Input/State combinations which can never occur 
> because some Inputs are generated internal to a object, and due to the 
> state machine of the object those inputs can only occur when in certain 
> states.  The success/failure input generated by an Attempt method fall 
> into this category, since they only occur in the Attempt state.
> 
> Then there are Input/State combinations that can never occur for a the 
> particular multi-component SM.
> 
> In fact, it would be very useful for analysis purposes to tag certain 
> input/state combinations with warnings, so that if our SM analysis shows 
> that input/state comination is possible for our application, a warning 
> is generated so that we know that we should redesign our application so 
> that it can't occur.  This is similar to something you mentioned at the 
> meeting, about certain input/state combinations being not valid.
> 
> Does this make sense?  Maybe I'm going into a bit too much depth, here.
> 
> - David
> 
> Kevin Gary wrote:
> 
>> At the 1-year review meeting with came away with some decisions w.r.t.
>> state machines that I do not see documented in the requirements. 
>> Specifically,
>> moving all appropriate component state machines to the "AttemptTo" 
>> pattern,
>> and ensuring all state machine transition tables are fully populated. 
>> I do
>> not see this in the requirements list - may I add them? Luis, should 
>> it be
>> you?
>>
>> I'm asking because we are working through our requirements for a 
>> validation
>> tool that includes static structural analysis of IGSTK state machines,
>> and these would be two things we check for.
>>
>> The fully populated state transition table is a particularly 
>> interesting one,
>> as to do exhaustive testing, here are some of the numbers for some of 
>> our SMs:
>>
>> Class        #States        #Inputs        Node    Edge    Path
>> View        2        15        1    15    225
>> Tracker        10        9        9    90    9^10
>> PulseGenerator    4        7        3    28    7^4 (2401)
>> Spatial Object    4        10        3    40    10^4 (10k)
>> Landmark3DReg.    9        7        8    63    7^9 (> 40M)
>> SerialCommun.    11        11        10    121    11^11 (>285M)
>>
>> The numbers for node, edge, and path indicate number of test cases 
>> required,
>> with some assumptions (no loops, path length = #nodes). In practice path
>> tests could be much higher. Then if we do scenarios across multiple 
>> component
>> SMs...
>>
>> Thanks,
>> Kevin G.
>>
>>
>> ------------------------------------------------------------------------
>>
>> _______________________________________________
>> IGSTK-Developers mailing list
>> IGSTK-Developers at public.kitware.com
>> http://public.kitware.com/cgi-bin/mailman/listinfo/igstk-developers
>>  
>>
> 

-- 
===
Kevin A. Gary, Ph.D.
Assistant Professor
DCST, ASU East
(480)727-1373
http://kgary2.east.asu.edu
kgary at asu.edu
-------------- next part --------------
A non-text attachment was scrubbed...
Name: kgary.vcf
Type: text/x-vcard
Size: 369 bytes
Desc: not available
URL: <http://public.kitware.com/pipermail/igstk-developers/attachments/20051214/1693f258/attachment.vcf>