lezione6

 Software Analysis and Testing (II)Lezione 6: 

Software Analysis and Testing (II) Lezione 6 Filippo Ricca ITC-Irst Istituto per la ricerca Scientifica e Tecnologica ricca@itc.it

Project Steps: 

Project Steps 1. Instrumentare il codice C usando TXL. Scrivere Testcases t.c. vi sia la copertura (100%) dei branch. 2. Fase di reverse engineering. Ricavare alcuni diagrammi (call graph e dipendenza tra funzioni e strutture dati). 3. Fase di Object identification (concept analysis). 4. UML design. 5. Generazione di codice Java (usare TXL per trasformazioni …). 6. Regression testing con i Testcases generati al punto 1. 7. Instrumentare il codice Java e aggiungere nuovi Testcases al fine di avere la copertura dei comandi/branch del nuovo codice.

Papers: 

Papers Identifying Modules via Concept Analysis. Michael Siff and Thomas Reps. 2. …

Object Identification: 

Object Identification Legacy systems usually have a monolithic style that makes maintenance an arduos task. “Object” identification: identifing possible ways of partitioning the program into modules (in C modules=functions+structs). A lot of methods exists, but the problem is not resolved (research). Experimental results are needed. How to apply concept analysis to the modularization problem?

Concept Analysis: 

Concept Analysis Concept analysis provides a way to identify grouping of objects that have common attributes. Given a context (O, A, R) Concept analysis Concepts (maximal collection of objects sharing common attributes) objects attributes binary relation between O and A

Concept analysis: example: 

Concept analysis: example ({cats, dogs}, {four-legged, hair covered}) is a concept. ({cats, chimpanzees}, {hair covered}) is not a concept. “this is not a maximal collection of objects sharing common attributes (dogs)”

Concept lattice: 

Concept lattice A concept (x0, y0) is a subconcept of concept (x1, y1) if x0  x1 example: ({dolphins, whales}, {intelligent, marine}) is a subconcept of ({dolphins, whales, humans, chimpanzees}, {intelligent}) The subconcept relation forms a concept lattice over the set of concepts

Concept lattice: example: 

Concept lattice: example top c4 c5 c3 c0 c1 c2 bot

Using concept analysis to identify potential objects: 

Using concept analysis to identify potential objects The process: 1) Build a context, where objects are functions and attributes are properties of those functions. - struct: return type, has argument, uses fields. - global variables: uses 2) Construct the concept lattice from the context. 3) Identify concept partitions – collections of concepts that partition the set of objects (example: c3, c2, c0)

Stack and queue example: 

Stack and queue example Stack: 3 base sp initStack isEmptyStack push pop Queue: 1 2 3 Front Back 1 2 3 “Implemented using 2 stacks” initQ isEmptyQ enq deq

Slide11: 

struct stack {int* base; int* sp; int size}; struct queue {struct stack* front; struct stack* back;}; struct stack* initStack(int sz) { struct stack* s=(struct stack*)malloc(sizeof(struct stack)); s->base=s->sp=(int*)malloc(sz*(sizeof(int))); s->size=sz; return s;} struct queue* initQ() { struct queue* s=(struct queue*)malloc(sizeof(struct queue)); q->front=initStack(SIZE); q->back=initStack(SIZE); return q;} int isEmptyStack(struct stack* s){return (s->sp ==s->base);} int isEmptyQ(struct queue* q) { return (isEmptyStack(q->front)&&isEmptyStack(q->back));} void push(struct stack* s, int i) { *(s->sp)=i; s->sp++; } void enq(struct queue* q, int i) { push(q->front, i); } int pop(struct stack* s) { if (isEmptyStack(s) return –1; s->sp--; return(*(s->sp)); } int deq(struct queue* q) { if (isEmptyQ(q)) return –1; if (isEmptyStack(q->back)) while(!isEmptyStack(q->front)) push(q->back, pop(q->front)); return pop(q->back); }

Applying concept analysis to our example (1): 

Applying concept analysis to our example (1) Objects O1, …, O7 are functions. Attributes A1, …, A5 are properties of functions.

Applying concept analysis to our example (2): 

Applying concept analysis to our example (2) top c4 c5 c0 c2 c1 c3 bot

Applying concept analysis to our example (3): 

Applying concept analysis to our example (3) 2 objects: Queue and Stack! One of the advantages of using concept analysis is that multiple possibilities for modularization are offered. Partitions: c0, c1, c2, c3 c4, c5 top

Using “negative” information: 

Using “negative” information If the code is “more tangled” it is possible to use “negative” information. Examples: Return type is not … Has not argument … Does not use fields … Now Suppose the functions are: int isEmptyQ(struct queue* q){ return (q->front->sp == q->front->base && q->back->sp == q->back->base); } void enq(struct queue*, int i){ *(q->front->sp)=i; q->front->sp++ }

New example: 

New example top c7 c5 c3 c2 c0 c6 c1 bot

“negative” information: new example: 

“negative” information: new example top c7 c5 c3 c0 c6 c1 bot c2 c4 2 objects: C4 and C5 Stack concept Queue concept

Partitions: 

Partitions Because of overlaps between concepts, not every group of concepts represents a potential modularization (group of objects). Feasible modularization are partitions: “collections of modules that are disjoint, but include all the functions” In the paper “Identifying Modules Via Concept Analysis” is presented an algorithm that computes partitions ….

ToscanaJ: 

ToscanaJ ToscanaJ is a Formal Concept Analysis tool. It is composed of 3 programs: ToscanaJ: the viewer Elba: editor Siena: permits to import “context” and visualizes them

Siena: 

Siena B Prova 3 3 O1 O2 O3 A1 A2 A3 xxx xx. x.. File

Laboratory: 

Laboratory Download ToscanaJ Mammal example (using Elba and Siena) Write TXL rules that build the context for chull.c (Siena format) Visualize the concept lattice. Find possible useful partitions (implement algorithm?) (first tentative) Attributes: uses fields of tVertex uses fields of tEdge uses fields of tFace Satisfied? If no proceed …(negative information)