Detecting Call Graph Unsoundness without Ground Truth

1. 문제 제기 (Problem)

자바 정적 분석 프레임워크 (Static Analysis Frameworks) 는 보안, 신뢰성, 성능 최적화 등 다양한 하위 애플리케이션의 핵심 인프라로 사용됩니다. 그러나 기존 연구와 평가 방식에는 다음과 같은 근본적인 한계가 존재합니다.

• Ground Truth(정답) 의 부재: 실제 대규모 프로그램에 대해 어떤 호출 그래프가 '정확한지' 알 수 있는 기준 (Ground Truth) 을 구축하는 것은 거의 불가능합니다.
• 단순한 오류와 다른 '의미론적 위반 (Semantic Violations)': 분석 도구가 크래시나 메모리 누수 같은 명백한 오류를 일으키지 않더라도, 분석 결과 (호출 그래프) 가 이론적으로 기대되는 속성 (예: 더 정밀한 분석이 덜 정밀한 분석의 결과를 포함해야 함) 을 위반하는 경우가 많습니다. 이러한 '침묵하는 오류'는 보안 취약점 (예: Log4Shell) 을 놓치게 하는 치명적인 원인이 됩니다.
• 비모순적 구성에 대한 잘못된 가정: 기존 평가는 분석 알고리즘과 설정 (Configuration) 이 단조롭게 구성되어 서로 다른 도구 간에 의미적으로 비교 가능한 결과를 산출한다고 가정합니다. 하지만 현대 자바 언어 기능 (람다, 리플렉션 등) 의 등장으로 이 가정이 깨지고 있습니다.

2. 방법론 (Methodology)

저자들은 Ground Truth 가 없는 환경에서도 의미론적 불일치를 감지할 수 있는 변형 테스트 (Metamorphic Testing) 기반의 새로운 방법론을 제안합니다.

• 부분 순서 (Partial Order) 기반의 시맨틱 계약:

  • 분석 알고리즘과 설정은 정밀도 (Precision) 와 건전성 (Soundness) 에 따라 부분 순서 관계를 가집니다.
  • 정밀도 순서: 더 정밀한 분석 (예: RTA) 은 덜 정밀한 분석 (예: CHA) 보다 거짓 긍정 (False Positive) 을 더 적게 포함해야 합니다.
  • 건전성 순서: 더 건전한 분석은 덜 건전한 분석보다 모든 유효한 호출 엣지 (True Positive) 를 포함해야 합니다.
  • 핵심 아이디어: 외부 오라클 (Ground Truth) 이 없더라도, "더 정밀한 설정/알고리즘이 덜 정밀한 것보다 더 많은 엣지를 추가하거나 (건전성 위반), 불필요한 엣지를 제거하는 (정밀도 위반) 경우"를 감지하여 이를 '의미론적 위반'으로 간주합니다.

• 테스트 범위:

  • 내부 프레임워크 테스트: 단일 프레임워크 내에서 알고리즘 간, 설정 간, 그리고 알고리즘 - 설정 조합 간의 일관성을 검증합니다.
  • 교차 프레임워크 테스트: 서로 다른 프레임워크 (Soot, SootUp, WALA, Doop) 가 동일한 바이트코드를 분석할 때 기대되는 이론적 순서 관계가 유지되는지 확인합니다.

• 전처리 (Normalization): 프레임워크마다 다른 중간 표현 (IR) 과 메타데이터 (메모리 주소, 랜덤 ID 등) 로 인한 비교 왜곡을 방지하기 위해 호출 그래프를 정규화 (Method Signature 통일, 불필요한 노드 제거) 하는 파이프라인을 구현했습니다.

3. 주요 기여 (Key Contributions)

1. Ground Truth 없는 검증 방법론 도입: 정밀도 및 건전성 관계를 '테스트 가능한 시맨틱 계약'으로 간주하여, 레이블이 없는 환경에서도 체계적인 테스트를 가능하게 했습니다.
2. 알고리즘과 설정의 통합적 부분 순서 확장: 기존에 분리되어 연구되던 알고리즘과 설정을 통합하여, 알고리즘 - 설정 상호작용에서 발생하는 시맨틱 불일치를 포착할 수 있게 했습니다.
3. 대규모 실증 연구 수행: 4 개의 주요 자바 정적 분석 프레임워크 (Soot, SootUp, WALA, Doop) 에 대해 광범위한 실험을 수행하여 이전에 문서화되지 않은 수많은 위반 사례와 현대 자바 기능 (람다, 리플렉션 등) 으로 인한 실패 패턴을 규명했습니다.

4. 실험 결과 (Key Results)

연구는 4 개의 프레임워크 (Soot, SootUp, WALA, Doop) 와 JCG 벤치마크를 사용하여 수행되었으며, 다음과 같은 주요 발견을 도출했습니다.

• RQ1: 프레임워크 내부 설정 위반:

  • WALA: 정밀도 설정 (객체 민감성, 필드 민감성) 을 활성화하면 오히려 호출 그래프가 크게 변형되어 예상된 정밀도 순서가 위반되는 경우가 많았습니다. 특히 리플렉션 처리 방식에서 기인한 추론적 복구 (Speculative Recovery) 가 새로운 엣지를 추가하며 정밀도 순서를 깨뜨렸습니다.
  • Soot: 설정 변경에 따른 정밀도 순서 위반은 상대적으로 적었으나, 알고리즘 간 상호작용에서 문제가 발생했습니다.

• RQ2: 알고리즘 간 일관성 위반:

  • 이론적으로 더 정밀한 알고리즘 (예: VTA) 이 덜 정밀한 알고리즘 (예: CHA) 의 결과를 포함해야 함에도 불구하고, 실제 구현에서는 유효한 호출 엣지를 누락하거나 (건전성 위반), 불필요한 엣지를 추가하는 경우가 빈번했습니다.
  • SootUp vs Soot: SootUp 의 CHA 는 람다 식 (invokedynamic) 을 처리하지 못해 호출 그래프를 잘라내지만, Soot 의 RTA 는 이를 해결합니다. 이는 이론적 정밀도 순서와 실제 동작이 반대되는 '건전성 역전 (Soundness Inversion)' 사례입니다.

• RQ3: 알고리즘과 설정의 상호작용 (Synergistic Failures):

  • 알고리즘 변경과 설정 변경을 동시에 적용했을 때, 각각의 변화만 있을 때보다 위반 사례가 기하급수적으로 증가하는 '시너지 효과'가 관찰되었습니다. 예를 들어, 객체 민감성 (OS) 설정이 리플렉션 엣지를 추가하고, 이를 흐름 민감성 알고리즘이 전파하면서 예상치 못한 오류가 증폭되었습니다.

• RQ4: 교차 프레임워크 간 의미론적 격차:

  • 근본적인 불일치: Soot 와 WALA, SootUp 와 WALA 간의 호출 그래프 유사도는 매우 낮았습니다 (약 10~21%). 이는 단순한 구현 오류가 아니라, 리플렉션 처리, 진입점 (Entry Point) 정의, 네이티브 코드 모델링 등 프레임워크의 설계 철학 차이에서 기인한 '해결 불가능한 의미론적 격차 (Irreconcilable Semantic Gaps)'임을 보여주었습니다.
  • Doop 의 특수성: Doop 는 논리 규칙을 통해 네이티브 및 런타임 흐름까지 모델링하여 호출 그래프 크기가 압도적으로 크며, 다른 프레임워크와의 유사도 지표 (Jaccard Index) 는 0 에 수렴했습니다. 이는 분석 범위의 차이에서 비롯된 것이지, 논리 오류가 아님을 시사합니다.

• 위반 원인 분포:

  • 정적 초기화 (<clinit>) 관련 위반이 약 45% 로 가장 많았으며, 동적 호출 및 람다 (30%), 리플렉션 (15%) 순으로 발생했습니다.

5. 의의 및 결론 (Significance & Conclusion)

이 연구는 정적 분석 분야에 다음과 같은 중요한 통찰을 제공합니다.

• 평가 패러다임의 전환: "Ground Truth 가 없으면 분석 도구를 평가할 수 없다"는 기존 관념을 깨고, 부분 순서 (Partial Order) 를 활용한 내부 일관성 검증을 통해 신뢰할 수 있는 평가 체계를 제시했습니다.
• 현대 언어 기능의 취약점: 람다, 리플렉션, invokeDynamic 등 현대 자바 기능은 정적 분석 프레임워크 간의 일관성을 해치는 주요 원인이며, 각 프레임워크가 이를 해석하는 방식이 근본적으로 다름을 증명했습니다.
• 실용적 한계 (Precision Ceiling): 이론적으로 더 높은 정밀도를 추구할수록 계산 비용이 기하급수적으로 증가하여 실제로는 실행 불가능해지는 '정밀도의 한계'가 존재함을 발견했습니다.
• 향후 방향: 정적 분석 도구의 신뢰성을 높이기 위해서는 알고리즘, 설정, 그리고 프레임워크의 시맨틱을 분리하여 평가하는 것이 아니라, 이들의 상호작용을 통합적으로 고려해야 함을 강조합니다.

결론적으로, 이 논문은 정적 분석 프레임워크의 '침묵하는 오류'를 감지하고, 개발자가 구현 결함과 설계적 한계를 구분할 수 있도록 돕는 강력한 진단 도구와 방법론을 제시했습니다.