TTCN-3 Test Data Analyser Using Constraint Programming

TTCN‐3 Test Data Analyzer using  Constraint Programming Diana Vega, Ina Schieferdecker,  George Din, Stefan Taranu

Content • • • • • • •

Motivation Test Specification Quality Model TTCN‐3 Data Analysis Distance Metrics for TTCN‐3 Templates Constraint Programming  Example Conclusions

Motivation • The Problem – Test specification size increases more and more (e.g. 40.000 LOC for SIP TTCN‐ 3 test suite) – Lack of common methodologies for the assessment of the quality of test  specifications – Quality evaluation of test specifications ?

•

One View of the Problem – Test Data Variance [Metrics] • Test Specification Quality Model derived from ISO 9126 – joint work with  Univ. of Göettingen

– Test Effectivity [Characteristic] » Test Coverage [Sub‐characteristic] Test System Interface (TSI) coverage measure 

Related Work – Quality of tests White Box Testing ¾ SUT is transparent to the test

¾Coverage measures: ¾Statement coverage ¾Branch coverage ¾Block coverage ¾ …etc. ¾But … ¾ Syntactic coverage Different Coverage Measures!!!

Test Suite

SUT SUT SUT

1 2… n

Specification

Test Specification Quality Model Test Specification  Quality Test Effectivity Suitability Test  Coverage Accuracy Test  Correctness

Reliability

Usability

Efficiency

Maintainability

Portability

Reusability

Maturity

Understand‐ ability

Time Behaviour

Analysability

Adaptability

Coupling

Resource  Utilisation

Portability Compliance

Flexibility

Changeability

Test  Repeatability

Learnability

Fault‐Tolerance Operability Fault‐Revealing Capability

Test Effectivity  Functionality Compliance Compliance

Security Recoverability Reliability Compliance

Test  Evaluability Usability Compliance

Efficiency Compliance

Comprehen‐ sibility Stability Maintainability Compliance

Reusability Compliance

TTCN‐3 Data Analysis Data variance in TTCN‐3  Terminology

Test System

¾1. SUT is represented by TSI ¾set of ports of different port  types allowing various data  types

Data Quantification

TSI

¾“system” clause in test case  definition

Port

¾2. TSI coverage – data input space Data Distance Size and complexity of potential data space

System under Test

¾Quantitative similarity  Ædistance measures ¾Qualitative similarity  Æpartitioning method

¾3. Assumption ¾all TSI ports are message‐ based port 6

Data Templates Construction • Concrete values • • • • •

Variables Function calls (user defined, predefined) Parameters (test case, function, module) Received templates Expressions How to solve them?

Constraint Programming (CP) • Control Flow Graph (CFG) – is a graph abstraction of the program, 

• CFG Symbolic Execution – by selecting only one execution path from the CFG – instead of supplying the normal inputs to a  program, supplies symbols representing arbitrary  values within a specific domain or constrained  values

CFG Example

p1 : (start) ‐‐> (1; 2) ‐‐> (3) ‐‐> (end) p2 : (start) ‐‐> (1; 2) ‐‐> (3) ‐‐> (4) ‐‐> (6) ‐‐> (3) ‐‐> (end)

Method applied to TTCN‐3 Tests Interfaces  Identification (TSIs)

‐ collect all test cases having the same TSI ‐ determine all the ports associated with each TSI

Template  Subset Selection

‐ currently only message based port are supported ‐ collection of messages associated to a port

Apply Constraint  Programming

‐ template solving using constraint programming

Distances Computation

‐ based on the distance formula

Template Partitioning

‐ select a partitioning method ‐ create a number of partitions

Compute  Coverage

‐ count the number of partitions ‐ compute coverage

Distance Computation Basic Type

Distance based on

Definition of distance d for values x and y

Integer

One-Dimensional Euclidian Distance

d (x, y) =

|x− y| sizeof ( Integer )

One-Dimensional Euclidian Distance

d (x, y) =

|x− y| sizeof ( Float )

Float

Boolean

Inequality d (x, y) =

Bitstring

Hamming Distance

{

0 for x=y 1 otherwise

number of positions for which the bits are different (the shorter bitstring is extended into the longer bitstring by filling it with leading ‘0’B) divided by the longer length: σ (x, y) d (x, y) =

maxlength (x, y)

with σ (x, y) = number of i where xi≠ yi Hexstring

Hamming Distance

same, but with leading ‘0’H

Octetstring

Hamming Distance

Same, but with leading ‘0’O

Charstring

Hamming Distance

Same, but with leading “” (spaces)

Universal Charstring

Hamming Distance

Same, but with leading “” (spaces)

Distance Computation Structured Type

Distance based on

Record

N-Dimensional Euclidian Distance

Definition of distance d for values x and y n

d (x, y) =

∑

( d ( x i , y i )) 2

i =1

n

Record of

n

Hamming Distance d (x, y) =

∑

i = 1

σ (x, y)

maxlength (x, y) where d (x, y) = number of i where d (xi, yi) > and where the record sequence is extended into the longer record sequence by filling it with leading omit. Set

N-Dimensional Euclidian Distance

same as for record

Set of

Hamming Distance

same as for record of

Enumerated

Inequality d (x, y) =

| n( x) − n( y ) | n

where n is the sequentially numbered index of the enumeration Union

Distance defined above d (x, y) = d ( σ (x), σ (y) ) =

{

1 for σ (x) = σ (y) 0 otherwise

Template Solving Method •

for each template from the template set identify the TTCN‐3 behavioral  entity (e.g. testcase, function) where the statement p.send() 1. build the control flow graph (CFG) for that specific behavioral entity (e.g. testcase, function). 2. localize the target template (i.e. p.send()) to a  corresponding node in CFG; this node is called target node.  3. determine the path conditions for each path that connects the CFG  head with the target node. a) b) c)

4.

identify the decisions blocks and derive the constraints build a variable symbol table on a top down manner which stores for each  variable the constrained domain apply the constraints on the variables directly/indirectly involved in the structure  of the target template

expand the templates set with variations of the target template as  resulted from the different constraints on different paths.

Partition Method Number of partitions: the number of varying data of a value set for a given type #partitions T’ : ΠT’ →N  #partitions T’ (∅) = 0 V ≠∅ : #partitions T’ (V ) = 1 + #partitions T’ (V ’ )  V ‘ = V  \ partition T’ (v)  for v in V

Algorithm 1. If template set not null 2. Select the first template as partition pivot (pp) 3. For each template t from the template set (t!=pp) • Compute distance d (pp, t)  • if d (pp, t) = 1) { vRequest.stars := vRequest.stars‐1; p.send(vRequest); t.start; repeat; } else { setverdict(fail); }         } [] t.timeout { setverdict(inconc); } }   }

Templates Set without CP •

Set={requestTwoStarsTemplate, requestFiveStarsTemplate, vRequest}

•

Distance computation d(requestTwoStarsTemplate, requestFiveStarsTemplate) = 0,125  1/3, since the vRequest is a local  testcase variable which has been not resolved d(requestFiveStarsTemplate; vRequest) = 1 > 1/3

•

Partitions P1 = {requestTwoStarsTemplate; requestFiveStarsTemplate} P2 = {vRequest}

•

Coverage = 2/3

Constraints Identification

Template Set with CP • •

Identified 6 paths; each path provides a vRequest(Cpathi) Example Cpath6 : { vRequest := requestF iveStarsT emplate;   vRequest:stars >= 1; vRequest:stars := vRequest:stars‐1 }

•

Set={requestTwoStarsTemplate, requestFiveStarsTemplate, vRequest(Cpathi)}

•

Distance computation d(requestTwoStarsTemplate, requestFiveStarsTemplate) = 0,125