Regular Expressions and Flow Anomaly Detection in Software Testing Methodologies

The Problem

The Method

Limitations

The problem

The generic flow anomaly detection problem (note: not just data flow anomalies, but any flow anomaly) is looking for a particular sequence of options taking into consideration of all possible paths through a routine

Let the operations be SET and RESET, indicated by s and r respectively, and we want to know if there is a SET followed by a SET or a RESET followed immediately by RESET (as ss or an rr sequence)

Some more application examples:

     A file can be opened (o), closed (c), read (r) or written (w)

The sequence is nonsensical, if the file is read or written to after it's been closed. Therefore, cr and cw are anomalies

Likewise, just after opening, we may have a bug if the file is read before it's been written. Hence, or is also anomalies

Moreover, oo and cc, through not actual bugs, are a waste of time and therefore should also be examined

some more application examples:

A tape transport can do a rewind (d), fast-forward (f), read (r), write(w), stop (p) and skip (k)

Regarding the use of the transport there are rules;

Example: without an intervening stop you cannot go from rewind to fast forward or from rewind or fast forward to read or write without an intervening stop

The following graph lead to anomalous sequences on any path? If so, what sequences and under what circumstances?

       The data flow anomalies discussed in dataflow testing requires us to detect the dd, dk, kk, and ku sequences. Are there paths with anomalous dataflows?

The Method:

with the appropriate operator or the null operator 1,annotate each link in the graph

Using the fact that a+a = a 12 = 1, simplify things to the extent possible

You now have a regular expression that denotes all the possible sequences of operators in that graph. You can examine that regular expression for the sequence of interest

Example: Let A, B, C be nonempty sets of character sequences whose smallest string is at least one character doing

Let T be a two character string of characters

If T is substring of AB¹C (i.e., if T appears within), then T will appear in AB²C (HUANG's Theorem)

For example, Let

a=pp

B=srr

C=rp

T=ss

The theorem states that ss will appear in pp(srr)nrp if it appears in pp(srr)²rp.

However, let

A=p+pp+ps

B=psr+ps(r+ps)

C=rp

T=p⁴

Is it obvious that there is a p⁴ sequences in ABⁿC? the theorem state that we have to only look at (p+pp+ps) [psr(r+ps)²]rp

Multiplying out the expression and simplifying shows that there is no p⁴ sequences

Limitations

To cover sequences of greater length than two characters, Hugan's theorem can be easily generalized

Further than three characters, even if, things get complex and this method has probably reached its practical limit for manual application

For finding sequences that occur at the beginnings and ends of strings there are some theorems, but no algorithms for finding strings buried in an expression

Static flow analysis methods can't determine whether a path is achievable or not

The impact of unachievable paths will not be included in the analysis, unless the flow analysis includes symbolic execution or similar techniques

The flow anomaly application

Example: Doesn't tell us that there is a flow anomaly. It tells us that if the path is achievable, then there is a flow anomaly

Certainly such analytical problems go away. If you take the trouble to design routines for which all paths are achievable

Share on Google Plus

About Data Sciences by Venu

Hi, My name is Venugopala Chary and I'm Currently working as Associate Professor in Reputed Engineerng College, Hyderabad. I have B.Tech and M.tech in regular from JNTU Hyderabad. I have 11 Years of Teaching Experience for both B.Tech and M.Tech Courses.