Program Slicing

Nella programmazione informatica, il program slicing è il calcolo dell'insieme di istruzioni del programma, chiamato program slice, che può influenzare i valori in un punto di interesse, denominato criterio di slicing . Lo slicing del programma può essere utilizzato nel debug per individuare più facilmente la fonte degli errori. Altre applicazioni dello slicing includono la manutenzione del software, l'ottimizzazione, l'analisi dei programmi e il controllo del flusso di informazioni .

Le tecniche di slicing hanno visto un rapido sviluppo sin dalla definizione originale di Mark Weiser . Inizialmente lo slicing era solo statico, cioè applicato al codice sorgente senza altre informazioni oltre al codice sorgente. Bogdan Korel e Janusz Laski hanno introdotto lo slicing dinamico, che funziona su una specifica esecuzione del programma (per una data traccia di esecuzione).^[1] Esistono altre forme di slicing, ad esempio il path slicing.^[2]

Slicing statico

Basandosi sulla definizione originale di Weiser, informalmente, una porzione di slice statica S è costituita da tutte le istruzioni del programma P che possono influenzare il valore della variabile v in un'istruzione x. La sezione è definita per un criterio di slice C=(x,v) dove x è un'istruzione nel programma P e v è variabile in x. Una slice statica include tutte le istruzioni che possono influenzare il valore della variabile v nell'istruzione x per qualsiasi possibile input. Le slice statiche vengono calcolate ripercorrendo le dipendenze tra le istruzioni. Più specificamente, per calcolare la sezione statica per (x,v), troviamo prima tutte le istruzioni che possono influenzare direttamente il valore di v prima che venga incontrata l'istruzione x. Ricorsivamente, per ogni istruzione y che può influenzare il valore di v nell'istruzione x, calcoliamo le sezioni per tutte le variabili z in y che influenzano il valore di v. L'unione di tutte queste sezioni è la slice statica per (x,v) .

Esempio

Ad esempio, considera il programma C di seguito.

Calcoliamo la slice per ( write(sum), sum ). Il valore di sum è direttamente influenzato dalle affermazioni "sum = sum + i + w" se N>1 e "int sum = 0" se N <= 1. Quindi, slice( write(sum), sum) è l'unione di tre slice e l'istruzione "int sum = 0" che non ha dipendenze:

slice (sum = sum + i + w, sum)
slice (sum = sum + i +w, i)
slice (sum = sum +i +w, w), and
{int sum=0}

È abbastanza facile vedere che slice( sum = sum + i + w, sum) consiste di "sum = sum + i + w" e "int sum = 0" perché queste sono le uniche due istruzioni precedenti che possono influenzare il valore della somma in "sum = sum + i + w". Allo stesso modo, slice( sum = sum + i + w, i) contiene solo "for(i = 1; i < N; ++i) {" e slice( sum = sum + i + w, w) contiene solo l'istruzione "int w = 7".

Quando uniamo tutte queste istruzioni, non abbiamo codice eseguibile, quindi per rendere la slice eseguibile aggiungiamo semplicemente la parentesi graffa finale per il ciclo for e la dichiarazione di i. La sezione eseguibile statica risultante è mostrata sotto il codice originale riportato di seguito.

int i;
int sum = 0;
int product = 1;
int w = 7;
for(i = 1; i < N; ++i) {
 sum = sum + i + w;
 product = product * i;
}
write(sum);
write(product);

La slice eseguibile statica per i criteri ( write(sum), sum) è il nuovo programma mostrato di seguito.

int i;
int sum = 0;
int w = 7;
for(i = 1; i < N; ++i) {
 sum = sum + i + w;

}
write(sum);

In effetti, la maggior parte delle tecniche di slicing statiche, inclusa la tecnica di Weiser, rimuoveranno anche l'istruzione write(sum) . Poiché, nell'istruzione write(sum), il valore di sum non dipende dall'istruzione stessa. Spesso una slice per una particolare istruzione x includerà più di una variabile. Se V è un insieme di variabili in un'istruzione x, allora la sezione per (x, V) è l'unione di tutte le sezioni con criteri (x, v) dove v è una variabile nell'insieme V.

Approccio allo slicing statico rapido in avanti

Un approccio di slicing molto veloce e scalabile, ma leggermente meno accurato, è estremamente utile per una serie di motivi. Gli sviluppatori disporranno di costi molto bassi e di mezzi pratici per stimare l'impatto di un cambiamento in pochi minuti invece che in giorni. Questo è molto importante per pianificare l'implementazione di nuove funzionalità e comprendere come un cambiamento è correlato ad altre parti del sistema. Fornirà inoltre un test poco costoso per determinare se è giustificata un'analisi completa e più costosa del sistema. Un approccio di slicing rapido aprirà nuove strade di ricerca nelle metriche e nell’estrazione di storie basate sullo slicing. Cioè, ora lo slicing può essere condotto su sistemi molto grandi e su intere cronologie di versioni in tempi molto pratici. Ciò apre la porta a una serie di esperimenti e indagini empiriche che in precedenza erano troppo costosi da intraprendere.^[3]

Slicing dinamico

Lo slicing dinamico utilizza le informazioni su una particolare esecuzione di un programma. Una slice dinamica contiene tutte le istruzioni che effettivamente influenzano il valore di una variabile in un punto del programma per una particolare esecuzione del programma piuttosto che tutte le istruzioni che potrebbero aver influenzato il valore di una variabile in un punto del programma per qualsiasi esecuzione arbitraria del programma.

Un esempio per chiarire la differenza tra slicing statico e dinamico. Consideriamo una piccola parte di un'unità di programma, in cui è presente un blocco di iterazione contenente un blocco if-else. Ci sono alcune istruzioni in entrambi i blocchi if e else che hanno effetto su una variabile. Nel caso dello slicing statico, poiché l'intera unità di programma viene considerata indipendentemente da una particolare esecuzione del programma, le istruzioni interessate in entrambi i blocchi verrebbero incluse nello slice. Ma nel caso dello slicing dinamico consideriamo una particolare esecuzione del programma, in cui il blocco if viene eseguito e le istruzioni interessate nel blocco else non vengono eseguite. Ecco perché in questo particolare caso di esecuzione la sezione dinamica conterrebbe solo le istruzioni nel blocco if .

Note

^ vol. 29, DOI:10.1016/0020-0190(88)90054-3, https://oadoi.org/10.1016/0020-0190(88)90054-3.
^ Ranjit Jhala e Rupak Majumdar, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, PLDI '05, ACM, 2005, pp. 38–47, DOI:10.1145/1065010.1065016, ISBN 9781595930569.
^ (EN) vol. 26, DOI:10.1002/smr.1651, ISSN 2047-7473 (WC · ACNP), https://oadoi.org/10.1002/smr.1651.

Bibliografia

Mark Weiser. "Program slicing". Proceedings of the 5th International Conference on Software Engineering, pages 439–449, IEEE Computer Society Press, March 1981.
Mark Weiser. "Program slicing". IEEE Transactions on Software Engineering, Volume 10, Issue 4, pages 352–357, IEEE Computer Society Press, July 1984.
Susan Horwitz, Thomas Reps, and David Binkley, Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems, Volume 12, Issue 1, pages 26-60, January 1990.
Frank Tip. "A survey of program slicing techniques". Journal of Programming Languages, Volume 3, Issue 3, pages 121–189, September 1995.
David Binkley and Keith Brian Gallagher. "Program slicing". Advances in Computers, Volume 43, pages 1–50, Academic Press, 1996.
Andrea de Lucia. "Program slicing: Methods and applications", International Workshop on Source Code Analysis and Manipulation, pages 142-149, 2001, IEEE Computer Society Press.
Mark Harman and Robert Hierons. "An overview of program slicing", Software Focus, Volume 2, Issue 3, pages 85–92, January 2001.
David Binkley and Mark Harman. "A survey of empirical results on program slicing", Advances in Computers, Volume 62, pages 105-178, Academic Press, 2004.
Jens Krinke. "Program Slicing", In Handbook of Software Engineering and Knowledge Engineering, Volume 3: Recent Advances. World Scientific Publishing, 2005
Silva, Josep. "A vocabulary of program slicing-based techniques", ACM Computing Surveys, Volume 44, Issue 3, Association for Computing Machinery, June 2012
Alomari HW et al. "srcSlice: very efficient and scalable forward static slicing". Wiley Journal of Software: Evolution and Process (JSEP), DOI: 10.1002/smr.1651, Vol. 26, No. 11, pp. 931-961, 2014.

Voci correlate

Collegamenti esterni

VALSOFT/Progetto Joana
Progetto Indus (parte di Bandera Checker)
Progetto di slicing del programma del Wisconsin

[1] vol. 29, DOI:10.1016/0020-0190(88)90054-3, https://oadoi.org/10.1016/0020-0190(88)90054-3.

[2] Ranjit Jhala e Rupak Majumdar, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, PLDI '05, ACM, 2005, pp. 38–47, DOI:10.1145/1065010.1065016, ISBN 9781595930569.

[3] (EN) vol. 26, DOI:10.1002/smr.1651, ISSN 2047-7473 (WC · ACNP), https://oadoi.org/10.1002/smr.1651.

[1]

[2]

[3]