958:
149:
slice includes all the statements that can affect the value of variable v at statement x for any possible input. Static slices are computed by backtracking dependencies between statements. More specifically, to compute the static slice for (x,v), we first find all statements that can directly affect the value of v before statement x is encountered. Recursively, for each statement y which can affect the value of v in statement x, we compute the slices for all variables z in y that affect the value of v. The union of all those slices is the static slice for (x,v).
29:
505:
features and understanding how a change is related to other parts of the system. It will also provide an inexpensive test to determine if a full, more expensive, analysis of the system is warranted. A fast slicing approach will open up new avenues of research in metrics and the mining of histories based on slicing. That is, slicing can now be conducted on very large systems and on entire version histories in very practical time frames. This opens the door to a number of experiments and empirical investigations previously too costly to undertake.
1512:
1532:
1522:
526:
blocks that have an effect on a variable. In the case of static slicing, since the whole program unit is looked at irrespective of a particular execution of the program, the affected statements in both blocks would be included in the slice. But, in the case of dynamic slicing we consider a particular
157:
For example, consider the C program below. Let's compute the slice for ( write(sum), sum ). The value of sum is directly affected by the statements "sum = sum + i + w" if N>1 and "int sum = 0" if N <= 1. So, slice( write(sum), sum) is the union of three slices and the "int sum = 0" statement
175:
It is fairly easy to see that slice( sum = sum + i + w, sum) consists of "sum = sum + i + w" and "int sum = 0" because those are the only two prior statements that can affect the value of sum at "sum = sum + i + w". Similarly, slice( sum = sum + i + w, i) only contains "for(i = 1; i < N; ++i) {"
148:
Based on the original definition of Weiser, informally, a static program slice S consists of all statements in program P that may affect the value of variable v in a statement x. The slice is defined for a slicing criterion C=(x,v) where x is a statement in program P and v is variable in x. A static
504:
A very fast and scalable, yet slightly less accurate, slicing approach is extremely useful for a number of reasons. Developers will have a very low cost and practical means to estimate the impact of a change within minutes versus days. This is very important for planning the implementation of new
513:
Dynamic slicing makes use of information about a particular execution of a program. A dynamic slice contains all statements that actually affect the value of a variable at a program point for a particular execution of the program rather than all statements that may have affected the value of a
495:
is not dependent on the statement itself. Often a slice for a particular statement x will include more than one variable. If V is a set of variables in a statement x, then the slice for (x, V) is the union of all slices with criteria (x, v) where v is a variable in the set V.
179:
When we union all of those statements, we do not have executable code, so to make the slice an executable slice we merely add the end brace for the for loop and the declaration of i. The resulting static executable slice is shown below the original code below.
517:
An example to clarify the difference between static and dynamic slicing. Consider a small piece of a program unit, in which there is an iteration block containing an if-else block. There are a few statements in both the
872:
1535:
1525:
776:, and David Binkley, Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems, Volume 12, Issue 1, pages 26-60, January 1990.
693:
Alomari, Hakam W.; Collard, Michael L.; Maletic, Jonathan I.; Alhindawi, Nouh; Meqdadi, Omar (2014-05-19). "srcSlice: very efficient and scalable forward static slicing".
1097:
1295:
1194:
789:
Andrea de Lucia. "Program slicing: Methods and applications", International
Workshop on Source Code Analysis and Manipulation, pages 142-149, 2001,
1177:
133:
129:
140:, which works on a specific execution of the program (for a given execution trace). Other forms of slicing exist, for instance path slicing.
535:
block do not get executed. So, that is why in this particular execution case, the dynamic slice would contain only the statements in the
779:
Frank Tip. "A survey of program slicing techniques". Journal of
Programming Languages, Volume 3, Issue 3, pages 121–189, September 1995.
879:
799:
David
Binkley and Mark Harman. "A survey of empirical results on program slicing", Advances in Computers, Volume 62, pages 105-178,
796:
Mark Harman and Robert
Hierons. "An overview of program slicing", Software Focus, Volume 2, Issue 3, pages 85–92, January 2001.
806:
Jens Krinke. "Program
Slicing", In Handbook of Software Engineering and Knowledge Engineering, Volume 3: Recent Advances.
814:
114:
128:. At first, slicing was only static, i.e., applied on the source code with no other information than the source code.
1134:
652:
72:
50:
43:
752:. "Program slicing". Proceedings of the 5th International Conference on Software Engineering, pages 439–449,
1566:
1233:
110:
1394:
1248:
942:
907:
679:
Program Slices: Formal, Psychological, and
Practical Investigations of an Automatic Program Abstraction Method
1571:
1484:
957:
813:
Silva, Josep. "A vocabulary of program slicing-based techniques", ACM Computing
Surveys, Volume 44, Issue 3,
578:
1447:
966:
917:
1386:
782:
David
Binkley and Keith Brian Gallagher. "Program slicing". Advances in Computers, Volume 43, pages 1–50,
1422:
1341:
807:
762:. "Program slicing". IEEE Transactions on Software Engineering, Volume 10, Issue 4, pages 352–357,
118:
1452:
1172:
1561:
1515:
1043:
865:
707:
612:
1366:
1164:
37:
17:
1326:
1082:
1074:
637:
Proceedings of the 2005 ACM SIGPLAN conference on
Programming language design and implementation
483:
In fact, most static slicing techniques, including Weiser's own technique, will also remove the
1469:
1464:
1267:
986:
702:
607:
54:
1092:
998:
991:
790:
763:
753:
1262:
1257:
1144:
1020:
1008:
937:
548:
106:
86:
8:
1274:
1109:
981:
558:
553:
124:
Slicing techniques have been seeing a rapid development since the original definition by
1556:
1243:
1184:
1154:
1139:
1104:
1003:
947:
902:
728:
658:
1358:
932:
720:
648:
621:
841:
732:
1305:
1204:
1129:
1038:
888:
824:
769:
712:
662:
640:
617:
1409:
1119:
1028:
563:
846:
1427:
1310:
1238:
1218:
1124:
1087:
1053:
922:
800:
783:
773:
105:
to locate source of errors more easily. Other applications of slicing include
1550:
1114:
1048:
912:
724:
677:
644:
176:
and slice( sum = sum + i + w, w) only contains the statement "int w = 7".
1474:
1457:
1300:
927:
1290:
1149:
820:
759:
749:
125:
97:, that may affect the values at some point of interest, referred to as a
514:
variable at a program point for any arbitrary execution of the program.
1376:
1371:
823:
et al. "srcSlice: very efficient and scalable forward static slicing".
1437:
1253:
1033:
716:
572:
102:
852:
1336:
857:
1331:
1189:
568:
682:(PhD Thesis thesis). Ann Arbor, MI, USA: University of Michigan.
598:
Korel, Bogdan; Laski, Janusz (1988). "Dynamic
Program Slicing".
692:
499:
1489:
1479:
1399:
831:), DOI: 10.1002/smr.1651, Vol. 26, No. 11, pp. 931-961, 2014.
1442:
1417:
93:
is the computation of the set of program statements, the
1432:
635:
Jhala, Ranjit; Majumdar, Rupak (2005). "Path slicing".
531:
block gets executed and the affected statements in the
639:. PLDI '05. New York, NY, USA: ACM. pp. 38–47.
1548:
825:Wiley Journal of Software: Evolution and Process
571:a tool which implements slicing algorithms on
873:
634:
500:Lightweight forward static slicing approach
1531:
1521:
880:
866:
695:Journal of Software: Evolution and Process
597:
352:The static executable slice for criteria (
706:
611:
73:Learn how and when to remove this message
36:This article includes a list of general
356:, sum) is the new program shown below.
1549:
675:
527:execution of the program, wherein the
861:
887:
22:
815:Association for Computing Machinery
487:statement. Since, at the statement
13:
508:
42:it lacks sufficient corresponding
14:
1583:
853:Wisconsin Program-Slicing Project
835:
168:slice( sum = sum + i + w, w), and
143:
101:. Program slicing can be used in
16:For other uses of "slicing", see
1530:
1520:
1511:
1510:
956:
27:
162:slice( sum = sum + i + w, sum),
686:
669:
628:
600:Information Processing Letters
591:
1:
743:
579:Partial dead code elimination
165:slice( sum = sum + i + w, i),
622:10.1016/0020-0190(88)90054-3
7:
1234:Curry–Howard correspondence
808:World Scientific Publishing
676:Weiser, Mark David (1979).
542:
158:which has no dependencies:
10:
1588:
152:
15:
1506:
1408:
1385:
1357:
1350:
1319:
1283:
1226:
1217:
1163:
1073:
1066:
1019:
974:
965:
954:
895:
849:(part of Bandera checker)
584:
358:
182:
119:information flow control
18:Slicing (disambiguation)
1083:Abstract interpretation
645:10.1145/1065010.1065016
57:more precise citations.
1567:Program transformation
992:Categorical semantics
842:VALSOFT/Joana Project
791:IEEE Computer Society
764:IEEE Computer Society
754:IEEE Computer Society
1572:Software maintenance
938:Runtime verification
549:Software maintenance
107:software maintenance
87:computer programming
1195:Invariant inference
943:Safety and liveness
559:Reaching definition
554:Dependence analysis
1359:Constraint solvers
1185:Concolic execution
1140:Symbolic execution
948:Undefined behavior
903:Control-flow graph
756:Press, March 1981.
1544:
1543:
1502:
1501:
1498:
1497:
1213:
1212:
1062:
1061:
766:Press, July 1984.
99:slicing criterion
83:
82:
75:
1579:
1562:Program analysis
1534:
1533:
1524:
1523:
1514:
1513:
1410:Proof assistants
1355:
1354:
1224:
1223:
1071:
1070:
1044:Rewriting system
1039:Process calculus
972:
971:
960:
889:Program analysis
882:
875:
868:
859:
858:
737:
736:
717:10.1002/smr.1651
710:
690:
684:
683:
673:
667:
666:
632:
626:
625:
615:
595:
538:
534:
530:
525:
521:
494:
490:
486:
479:
476:
473:
470:
467:
464:
461:
458:
455:
452:
449:
446:
443:
440:
437:
434:
431:
428:
425:
422:
419:
416:
413:
410:
407:
404:
401:
398:
395:
392:
389:
386:
383:
380:
377:
374:
371:
368:
365:
362:
355:
348:
345:
342:
339:
336:
333:
330:
327:
324:
321:
318:
315:
312:
309:
306:
303:
300:
297:
294:
291:
288:
285:
282:
279:
276:
273:
270:
267:
264:
261:
258:
255:
252:
249:
246:
243:
240:
237:
234:
231:
228:
225:
222:
219:
216:
213:
210:
207:
204:
201:
198:
195:
192:
189:
186:
115:program analysis
78:
71:
67:
64:
58:
53:this article by
44:inline citations
31:
30:
23:
1587:
1586:
1582:
1581:
1580:
1578:
1577:
1576:
1547:
1546:
1545:
1540:
1494:
1404:
1381:
1346:
1320:Data structures
1315:
1279:
1209:
1200:Program slicing
1159:
1058:
1029:Lambda calculus
1015:
961:
952:
913:Hyperproperties
891:
886:
838:
746:
741:
740:
708:10.1.1.641.8891
701:(11): 931–961.
691:
687:
674:
670:
655:
633:
629:
613:10.1.1.158.9078
596:
592:
587:
564:Data dependency
545:
536:
532:
528:
523:
519:
511:
509:Dynamic slicing
502:
492:
491:, the value of
488:
484:
481:
480:
477:
474:
471:
468:
465:
462:
459:
456:
453:
450:
447:
444:
441:
438:
435:
432:
429:
426:
423:
420:
417:
414:
411:
408:
405:
402:
399:
396:
393:
390:
387:
384:
381:
378:
375:
372:
369:
366:
363:
360:
353:
350:
349:
346:
343:
340:
337:
334:
331:
328:
325:
322:
319:
316:
313:
310:
307:
304:
301:
298:
295:
292:
289:
286:
283:
280:
277:
274:
271:
268:
265:
262:
259:
256:
253:
250:
247:
244:
241:
238:
235:
232:
229:
226:
223:
220:
217:
214:
211:
208:
205:
202:
199:
196:
193:
190:
187:
184:
155:
146:
138:dynamic slicing
91:program slicing
79:
68:
62:
59:
49:Please help to
48:
32:
28:
21:
12:
11:
5:
1585:
1575:
1574:
1569:
1564:
1559:
1542:
1541:
1539:
1538:
1528:
1518:
1507:
1504:
1503:
1500:
1499:
1496:
1495:
1493:
1492:
1487:
1482:
1477:
1472:
1467:
1462:
1461:
1460:
1450:
1445:
1440:
1435:
1430:
1425:
1420:
1414:
1412:
1406:
1405:
1403:
1402:
1397:
1391:
1389:
1383:
1382:
1380:
1379:
1374:
1369:
1363:
1361:
1352:
1348:
1347:
1345:
1344:
1339:
1334:
1329:
1323:
1321:
1317:
1316:
1314:
1313:
1308:
1303:
1298:
1293:
1287:
1285:
1281:
1280:
1278:
1277:
1272:
1271:
1270:
1260:
1251:
1246:
1241:
1239:Loop invariant
1236:
1230:
1228:
1221:
1219:Formal methods
1215:
1214:
1211:
1210:
1208:
1207:
1202:
1197:
1192:
1187:
1182:
1181:
1180:
1178:Taint tracking
1169:
1167:
1161:
1160:
1158:
1157:
1152:
1147:
1142:
1137:
1132:
1127:
1125:Model checking
1122:
1117:
1112:
1107:
1102:
1101:
1100:
1090:
1085:
1079:
1077:
1068:
1064:
1063:
1060:
1059:
1057:
1056:
1054:Turing machine
1051:
1046:
1041:
1036:
1031:
1025:
1023:
1017:
1016:
1014:
1013:
1012:
1011:
1006:
996:
995:
994:
984:
978:
976:
969:
963:
962:
955:
953:
951:
950:
945:
940:
935:
933:Rice's theorem
930:
925:
923:Path explosion
920:
915:
910:
905:
899:
897:
893:
892:
885:
884:
877:
870:
862:
856:
855:
850:
844:
837:
836:External links
834:
833:
832:
818:
811:
804:
801:Academic Press
797:
794:
787:
784:Academic Press
780:
777:
767:
757:
745:
742:
739:
738:
685:
668:
653:
627:
606:(3): 155–163.
589:
588:
586:
583:
582:
581:
576:
566:
561:
556:
551:
544:
541:
510:
507:
501:
498:
359:
183:
173:
172:
171:{ int sum=0 }.
169:
166:
163:
154:
151:
145:
144:Static slicing
142:
81:
80:
35:
33:
26:
9:
6:
4:
3:
2:
1584:
1573:
1570:
1568:
1565:
1563:
1560:
1558:
1555:
1554:
1552:
1537:
1529:
1527:
1519:
1517:
1509:
1508:
1505:
1491:
1488:
1486:
1483:
1481:
1478:
1476:
1473:
1471:
1468:
1466:
1463:
1459:
1456:
1455:
1454:
1451:
1449:
1446:
1444:
1441:
1439:
1436:
1434:
1431:
1429:
1426:
1424:
1421:
1419:
1416:
1415:
1413:
1411:
1407:
1401:
1398:
1396:
1393:
1392:
1390:
1388:
1384:
1378:
1375:
1373:
1370:
1368:
1365:
1364:
1362:
1360:
1356:
1353:
1349:
1343:
1340:
1338:
1335:
1333:
1330:
1328:
1325:
1324:
1322:
1318:
1312:
1309:
1307:
1304:
1302:
1299:
1297:
1296:Incorrectness
1294:
1292:
1289:
1288:
1286:
1282:
1276:
1273:
1269:
1266:
1265:
1264:
1263:Specification
1261:
1259:
1255:
1252:
1250:
1247:
1245:
1242:
1240:
1237:
1235:
1232:
1231:
1229:
1225:
1222:
1220:
1216:
1206:
1203:
1201:
1198:
1196:
1193:
1191:
1188:
1186:
1183:
1179:
1176:
1175:
1174:
1171:
1170:
1168:
1166:
1162:
1156:
1153:
1151:
1148:
1146:
1143:
1141:
1138:
1136:
1133:
1131:
1128:
1126:
1123:
1121:
1118:
1116:
1115:Effect system
1113:
1111:
1108:
1106:
1103:
1099:
1096:
1095:
1094:
1091:
1089:
1086:
1084:
1081:
1080:
1078:
1076:
1072:
1069:
1065:
1055:
1052:
1050:
1049:State machine
1047:
1045:
1042:
1040:
1037:
1035:
1032:
1030:
1027:
1026:
1024:
1022:
1018:
1010:
1007:
1005:
1002:
1001:
1000:
997:
993:
990:
989:
988:
985:
983:
980:
979:
977:
973:
970:
968:
964:
959:
949:
946:
944:
941:
939:
936:
934:
931:
929:
926:
924:
921:
919:
916:
914:
911:
909:
906:
904:
901:
900:
898:
894:
890:
883:
878:
876:
871:
869:
864:
863:
860:
854:
851:
848:
847:Indus Project
845:
843:
840:
839:
830:
826:
822:
819:
816:
812:
809:
805:
802:
798:
795:
792:
788:
785:
781:
778:
775:
771:
770:Susan Horwitz
768:
765:
761:
758:
755:
751:
748:
747:
734:
730:
726:
722:
718:
714:
709:
704:
700:
696:
689:
681:
680:
672:
664:
660:
656:
654:9781595930569
650:
646:
642:
638:
631:
623:
619:
614:
609:
605:
601:
594:
590:
580:
577:
574:
570:
567:
565:
562:
560:
557:
555:
552:
550:
547:
546:
540:
515:
506:
497:
357:
181:
177:
170:
167:
164:
161:
160:
159:
150:
141:
139:
135:
131:
127:
122:
120:
116:
112:
108:
104:
100:
96:
95:program slice
92:
88:
77:
74:
66:
56:
52:
46:
45:
39:
34:
25:
24:
19:
1458:Isabelle/HOL
1275:Verification
1258:completeness
1199:
1150:Type systems
1093:Control flow
987:Denotational
928:Polyvariance
896:Key concepts
828:
698:
694:
688:
678:
671:
636:
630:
603:
599:
593:
516:
512:
503:
482:
351:
178:
174:
156:
147:
137:
134:Janusz Laski
130:Bogdan Korel
123:
111:optimization
98:
94:
90:
84:
69:
60:
41:
1387:Lightweight
1249:Side effect
1145:Termination
999:Operational
908:Correctness
817:, June 2012
774:Thomas Reps
760:Mark Weiser
750:Mark Weiser
136:introduced
126:Mark Weiser
63:August 2012
55:introducing
1551:Categories
1342:Union-find
1306:Separation
1244:Refinement
1110:Dependence
1009:Small-step
918:Invariants
821:Alomari HW
744:References
573:C programs
489:write(sum)
485:write(sum)
354:write(sum)
38:references
1557:Debugging
1438:HOL Light
1268:Languages
1254:Soundness
1173:Data-flow
1155:Typestate
1105:Data-flow
1034:Petri net
982:Axiomatic
967:Semantics
725:2047-7473
703:CiteSeerX
608:CiteSeerX
103:debugging
1536:Glossary
1516:Category
1453:Isabelle
1337:Hashcons
1311:Temporal
1227:Concepts
1067:Analyses
1004:Big-step
733:18520643
543:See also
1526:Outline
1332:E-graph
1205:Testing
1190:Fuzzing
1165:Dynamic
1130:Pointer
803:, 2004.
786:, 1996.
663:5065847
569:Frama-C
539:block.
344:product
311:product
305:product
212:product
153:Example
51:improve
1301:Linear
1284:Logics
1120:Escape
1075:Static
1021:Models
810:, 2005
793:Press.
731:
723:
705:
661:
651:
610:
117:, and
40:, but
1490:Twelf
1480:NuPRL
1475:Mizar
1448:Idris
1395:Alloy
1351:Tools
1291:Hoare
1135:Shape
1088:Alias
975:Types
729:S2CID
659:S2CID
585:Notes
469:write
338:write
326:write
1470:LEGO
1465:Lean
1443:HOL4
1423:Agda
1418:ACL2
1400:TLA+
1256:and
1098:kCFA
829:JSEP
721:ISSN
649:ISBN
533:else
524:else
522:and
421:<
260:<
132:and
1485:PVS
1428:Coq
1377:SMT
1372:SAT
1367:CHC
1327:BDD
713:doi
641:doi
618:doi
493:sum
475:sum
448:sum
442:sum
400:for
385:int
373:sum
370:int
361:int
332:sum
287:sum
281:sum
239:for
224:int
209:int
197:sum
194:int
185:int
85:In
1553::
1433:F*
772:,
727:.
719:.
711:.
699:26
697:.
657:.
647:.
616:.
604:29
602:.
537:if
529:if
520:if
478:);
430:++
347:);
335:);
269:++
121:.
113:,
109:,
89:,
881:e
874:t
867:v
827:(
735:.
715::
665:.
643::
624:.
620::
575:.
472:(
466:}
463:;
460:w
457:+
454:i
451:+
445:=
439:{
436:)
433:i
427:;
424:N
418:i
415:;
412:1
409:=
406:i
403:(
397:;
394:7
391:=
388:w
382:;
379:0
376:=
367:;
364:i
341:(
329:(
323:}
320:;
317:i
314:*
308:=
302:;
299:w
296:+
293:i
290:+
284:=
278:{
275:)
272:i
266:;
263:N
257:i
254:;
251:1
248:=
245:i
242:(
236:;
233:7
230:=
227:w
221:;
218:1
215:=
206:;
203:0
200:=
191:;
188:i
76:)
70:(
65:)
61:(
47:.
20:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.