프로그램 슬라이스

Program slicing
"슬라이싱"의 다른 용도는 슬라이싱(구분)을 참조하십시오.

컴퓨터 프로그래밍에서 프로그램 슬라이싱은 프로그램 문 집합, 즉 프로그램 슬라이스의 계산으로, 슬라이싱 기준이라고 불리는 관심 지점의 값에 영향을 미칠 수 있습니다.프로그램 슬라이싱을 디버깅에 사용하면 오류 발생원을 더 쉽게 찾을 수 있습니다.슬라이싱의 다른 응용 프로그램에는 소프트웨어 유지보수, 최적화, 프로그램 분석 및 정보 흐름 제어가 포함됩니다.

슬라이스 기술은 Mark Weiser에 의해 처음 정의된 이후 빠른 발전을 보여 왔습니다.처음에 슬라이스는 정적일 뿐이었다. 즉, 소스 코드 외에는 다른 정보가 없는 소스 코드에 적용되었다.Bogdan Korel과 Janusz Laski는 (특정 실행 [1]트레이스에 대해) 프로그램의 특정 실행에서 작동하는 동적 슬라이싱을 도입했습니다.다른 형태의 슬라이싱이 존재합니다. 예를 들어 경로 [2]슬라이싱입니다.

정적 슬라이스

Weiser의 원래 정의에 근거하여 비공식적으로 [3]정적 프로그램 슬라이스 S는 스테이트먼트 x의 변수 v의 값에 영향을 줄 수 있는 프로그램 P의 모든 스테이트먼트로 구성된다.슬라이스는 슬라이스 기준 C=(x,v)에 대해 정의됩니다. 여기서 x는 프로그램 P의 스테이트먼트이고 v는 x의 가변입니다. 정적 슬라이스는 가능한 입력에 대해 스테이트먼트 x의 변수 v의 값에 영향을 줄 수 있는 모든 스테이트먼트를 포함합니다.정적 슬라이스는 문 사이의 종속성을 역추적하여 계산됩니다.구체적으로 (x,v)에 대한 정적 슬라이스를 계산하려면 먼저 문 x가 발생하기 전에 v의 값에 직접 영향을 줄 수 있는 모든 문을 찾습니다.반복적으로 스테이트먼트 x의 v 값에 영향을 줄 수 있는 각 스테이트먼트 y에 대해 v의 값에 영향을 미치는 y의 모든 변수 z에 대한 슬라이스를 계산합니다.이러한 모든 슬라이스의 결합은 (x,v)의 정적 슬라이스입니다.

예

예를 들어, 아래의 C 프로그램을 생각해 봅시다.(write(sum), sum) 슬라이스를 계산합니다.합계의 값은 N>1인 경우 "sum = sum + i + w" 문장과 N <= 1인 경우 "int sum = 0" 문장의 직접적인 영향을 받습니다. 따라서 슬라이스(쓰기(sum), sum)는 세 조각과 종속성이 없는 "int sum = 0" 문장의 결합입니다.

  1. 슬라이스(합 = 합 + i + w, 합)
    2. ,
  2. 슬라이스(합계 = 합계 + i + w, i)
    3. ,
  3. 슬라이스(합계 = 합계 + i + w, w)
    4. ,그리고.
  4. { int sum = 0 }.

슬라이스(sum = sum + i + w, sum)가 "sum = sum + i + w" 및 "int sum = 0"으로 구성된다는 것은 매우 쉽게 알 수 있습니다. 왜냐하면 이러한 진술이 "sum = sum + i + w"에서 합의 값에 영향을 미칠 수 있는 유일한 선행 진술이기 때문입니다.마찬가지로 슬라이스(sum = sum + i + w, i)는 "for(i = 1; i < N; + + i) {"만을 포함하고 슬라이스(sum = sum + i + w, w)는 "int w = 7" 문만 포함합니다.

이러한 모든 문을 결합할 때는 실행 가능한 코드가 없기 때문에 슬라이스를 실행 가능한 슬라이스로 만들기 위해 for loop과 i 선언의 끝 괄호를 추가합니다.결과 정적 실행 파일 슬라이스는 아래 원래 코드 아래에 표시됩니다. 

int i; int 합 = 0; int 제품. = 1; int w = 7; 위해서(i = 1; i < > N; ++i) {   합 = 합 + i + w;   제품. = 제품. * i; } 쓰다(합); 쓰다(제품.);

기준의 정적 실행 파일 슬라이스(write(sum), sum)은 아래 표시된 새 프로그램입니다. 

int i; int 합 = 0; int w = 7; 위해서(i = 1; i < > N; ++i) {   합 = 합 + i + w;  } 쓰다(합);

사실, Weiser 자신의 기술을 포함한 대부분의 정적 슬라이싱 기술은 또한 제거될 것입니다.write(sum)진술.그 이후로, 성명서에서write(sum), 의 가치sum스테이트먼트 자체에 의존하지 않습니다.종종 특정 문 x의 슬라이스에는 변수가 두 개 이상 포함됩니다.V가 문 x의 변수 집합인 경우, (x, V)에 대한 슬라이스는 기준(x, v)과 모든 슬라이스의 결합입니다. 여기서 v는 집합 V의 변수입니다.

경량 전방 정적 슬라이스 방식

매우 빠르고 확장성이 뛰어나지만 정확도가 약간 떨어지는 슬라이싱 방식은 여러 가지 이유로 매우 유용합니다.개발자는 변경에 따른 영향을 며칠이 아닌 몇 분 안에 추정할 수 있는 매우 저렴한 비용과 실용적인 수단을 갖게 됩니다.이는 새로운 기능의 구현을 계획하고 변경이 시스템의 다른 부분과 어떻게 관련되어 있는지를 이해하는 데 매우 중요합니다.또, 시스템의 완전하고 고가의 분석이 보증되고 있는지를 판단하기 위해서, 저비용의 테스트도 실시합니다.빠른 슬라이싱 접근방식은 슬라이싱을 기반으로 한 측정지표 연구와 이력 마이닝의 새로운 길을 열 것입니다.즉, 슬라이스는 이제 매우 큰 시스템과 전체 버전 이력에 대해 매우 실용적인 시간 범위 내에서 수행할 수 있습니다.이로 인해 이전에는 비용이 너무 많이 들어 [4]수행할 수 없었던 수많은 실험과 경험적 조사가 가능해졌습니다.

동적 슬라이스

프로그램의 특정 실행에 대한 정보를 사용합니다.동적 슬라이스는 프로그램의 임의 실행을 위해 프로그램 포인트의 변수 값에 영향을 줄 수 있는 모든 문장이 아니라 프로그램의 특정 실행을 위한 프로그램 포인트의 변수 값에 실제로 영향을 미치는 모든 문을 포함합니다.

정적 슬라이싱과 동적 슬라이싱의 차이를 명확히 하는 예.if-else 블록을 포함하는 반복 블록이 있는 프로그램 단위의 작은 부분을 생각해 보십시오.양쪽 모두 몇 가지 진술이 있습니다.if그리고.else변수에 영향을 미치는 블럭.정적 슬라이스의 경우, 프로그램의 특정 실행에 관계없이 전체 프로그램 단위를 보기 때문에 두 블록의 영향을 받는 문장이 슬라이스에 포함됩니다.단, 동적 슬라이스의 경우 프로그램의 특정 실행을 고려합니다.if블록이 실행되어 의 영향을 받는 스테이트먼트가else블록이 실행되지 않습니다.그렇기 때문에 이 특정 실행 사례에서 동적 슬라이스는 다음 명령어의 문만 포함합니다.if차단합니다.

「 」를 참조해 주세요.

메모들

  1. ^ Korel, Bogdan; Laski, Janusz (1988). "Dynamic Program Slicing". Information Processing Letters. 29 (3): 155–163. CiteSeerX 10.1.1.158.9078. doi:10.1016/0020-0190(88)90054-3.
  2. ^ Jhala, Ranjit; Majumdar, Rupak (2005). Path Slicing. Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation. PLDI '05. New York, NY, USA: ACM. pp. 38–47. doi:10.1145/1065010.1065016. ISBN 9781595930569.
  3. ^ Weiser, Mark David (1979). Program Slices: Formal, Psychological, and Practical Investigations of an Automatic Program Abstraction Method (PhD Thesis thesis). Ann Arbor, MI, USA: University of Michigan.
  4. ^ Alomari, Hakam W.; Collard, Michael L.; Maletic, Jonathan I.; Alhindawi, Nouh; Meqdadi, Omar (2014-05-19). "srcSlice: very efficient and scalable forward static slicing". Journal of Software: Evolution and Process. 26 (11): 931–961. CiteSeerX 10.1.1.641.8891. doi:10.1002/smr.1651. ISSN 2047-7473.

레퍼런스

  • 마크 와이저."프로그램 슬라이스"제5회 소프트웨어 엔지니어링 국제회의의 진행, 439~449페이지, IEEE Computer Society Press, 1981년 3월.
  • 마크 와이저."프로그램 슬라이스"IEEE Transactions on Software Engineering, 제10권, 제4호, 352-357쪽, IEEE Computer Society Press, 1984년 7월.
  • Susan Horwitz, Thomas Reps 및 David Binkley, 의존성 그래프를 사용한 절차 간 슬라이싱, ACM Transactions on Programming Languages and Systems, 제12권, 제1호, 제26-60쪽, 1990년 1월.
  • 프랭크 팁"프로그램 슬라이스 기술 조사"프로그래밍 언어 저널 제3권 제3호, 121-189쪽, 1995년 9월.
  • 데이비드 빙클리와 키스 브라이언 갤러거."프로그램 슬라이스"컴퓨터의 진보, 제43권, 1~50쪽, 학술 출판사, 1996.
  • 안드레아 드 루시아."프로그램 슬라이스:방법과 응용 프로그램", 소스 코드 분석 및 조작에 관한 국제 워크숍, 142-149페이지, 2001, IEEE Computer Society Press.
  • 마크 하먼과 로버트 하이런스입니다"프로그램 슬라이싱 개요", Software Focus, 제2권, 제3호, 85~92페이지, 2001년 1월
  • 데이비드 빙클리와 마크 하먼입니다."프로그램 슬라이스에 관한 경험적 결과 조사", 컴퓨터의 발전, 제6권, 105-178쪽, Academic Press, 2004.
  • 옌스 크린케."프로그램 슬라이싱", 소프트웨어 엔지니어링 및 지식 엔지니어링 핸드북, 제3권: 최근 진보.World Scientific Publishing, 2005
  • 실바, 호세프"프로그램 슬라이싱 기반 기술의 어휘", ACM Computing Surveies, Volume 44, 제3호, 컴퓨터 기계 협회, 2012년 6월
  • Alomari HW 등"srcSlice: 매우 효율적이고 확장성이 뛰어난 정방향 슬라이스입니다."Wiley Journal of Software: 진화 및 프로세스(JSEP), DOI: 10.1002/smr.1651, Vol. 26, No. 11, 페이지 931-961, 2014.

외부 링크