프로그램 카운터 (명령 포인터) 값의 패턴을 사용하여 루프를 감지합니다.

Question

특정 코드를 실행하는 동안 프로그램 카운터가 취하는 값의 시퀀스가 ​​있습니다. 이를 사용하여이 실행 파일을 생성 한 원본 코드에 대한 정적 분석을하고 싶습니다 (원래 코드는 사용할 수 없음) - 특히 몇 개의 루프가 있고 어떻게 중첩되어 있는지. 예를 제공하기 위해,이 경우

A: for() 
B:  if() 
C:   ... 
D:  else 
E:   ... 
F:  for() { 
G:   ... 
H:   ... 
I:  } 

, 프로그램 카운터 순서는 다음과 같을 수 있습니다 ABCDF {GHIGHIGHI} abdef와 {GHIGHI} abdef와 내가 얻을 수있는 방법 {GHIGHIGHIGHI} 위의 순서에서

, 아이디어 두 개의 루프가 있고 하나는 다른 루프 안에 중첩되어 있습니까? 적절한 구문 분석 기술을 사용하는 포인터 만 있으면 도움이 될 것입니다.

원본 코드에서 goto가없고 컴파일러에 최적화 된 루프 언 롤링과 같은 간단한 가정이있을 수 있습니다.

Answer 1

1. 각 프로그램 카운터가 정점이고 시퀀스의 연속적인 프로그램 카운터의 각 쌍이 방향성있는 가장자리 인 그래프를 프로그램 카운터 시퀀스에서 만듭니다. 하나의 꼭지점에서 다른 꼭지점까지 여러 가장자리가 있다면 그 중 하나만 유지하십시오.
2. 시퀀스의 첫 번째 프로그램 카운터에 의해 생성 된 정점에서 시작하여 깊이 우선 검색을 수행하여 사이클을 찾습니다. 각주기가 발견되면이주기의 마지막 가장자리를 별도의 목록으로 이동하십시오.
3. 모든주기를 찾아 그래프 밖으로 이동하면 DAG (directed acyclic graph)가 나타납니다. 이 DAG에 대해 토폴로지 정렬을 수행하여 if/else 블록 ('if'및 'else'중 어느 것이 프로그램 카운터 시퀀스에서 확인할 수없는 경우를 제외하고는 소스 코드와 마찬가지로 프로그램에서 올바른 명령문 시퀀스를 복원합니다.). 적절한 결과를 얻으려면 토폴로지 정렬이 특정 순서를 지정하지 않는 경우 깊이 우선 검색 순서를 사용해야합니다. while/for 루프 바디를 적절하게 배치하려면 2 단계의 몇 가지 추가 정보를 사용할 수 있습니다. 루프 감지 알고리즘이 각 루프의 두 번째 노드를 표시 할 수 있습니다.
4. if/else 블록을 분석하려면 그래프에서 스플릿/병합의 별도 목록을 만듭니다.
5. 루프 목록 (2 단계에서 추출)과 if/else (4 단계에서 추출) 목록을 하나의 간격 목록으로 결합하십시오. 모든 for/if/else 문에 대한 트리를 구성하려면이 간격의 관계를 사용하십시오 (다른 하나는 중첩됩니다).
6. 'while'루프의 끝에있는 'if'블록 while{...if{}}이 'while'및 'loop'의 시작 주소가 같은 {loop {} ...}와 같이 잘못 감지 될 수 있습니다. 'while'의 시작 주소는 중첩 된 루프의 시작 주소와 일치 할 수 없으므로 while{...if{}}으로 쉽게 후 처리 할 수 ​​있습니다. 중첩 된 'do-while'루프는 시작 주소가 같을 수 있지만 중첩 된 'if'에는 아무런 문제가 없습니다.

---

이 방법은 더 '고토', '휴식', 또는 사이클 중 다른 점프 때 루프는 하나의 상태를 점검 '에 대한'가없는 경우에만 간단한 경우에 작동합니다.