NESA: Relational Neuro-Symbolic Static Program Analysis

1. 문제 정의 (Problem)

정적 프로그램 분석 (Static Program Analysis) 은 코드 최적화, 버그 탐지, 디버깅 등에 필수적이지만, 실제 산업 현장에서의 채택은 다음과 같은 두 가지 주요 한계로 인해 제한받고 있습니다.

1. 컴파일 의존성 (Reliance on Compilation): 기존 주요 분석 도구들 (FlowDroid, Infer 등) 은 소스 코드를 중간 표현 (IR) 으로 변환하는 컴파일 과정에 의존합니다. 이로 인해 개발 환경에서 코드가 불완전한 상태일 때 분석이 불가능하며, 다양한 빌드 시스템과 컴파일러 버전 호환성 문제로 인해 IR 접근이 어렵습니다.
2. 커스터마이징의 부재 (Lack of Customization): 개발자의 특정 요구사항에 맞춰 분석 도구를 수정하거나 새로운 버그 패턴을 탐지하려면, 도메인 특화 언어 (DSL) 나 IR 내부 구조에 대한 깊은 전문 지식이 필요합니다. 이는 분석 도구의 진입 장벽을 높여 사용성을 떨어뜨립니다.

최근 대규모 언어 모델 (LLM) 은 컴파일 없이 코드 의미론을 이해할 수 있는 잠재력을 보였으나, 할루시네이션 (Hallucination, 거짓 정보 생성) 이라는 본질적인 문제로 인해 정적 분석과 같은 정밀도가 요구되는 작업에서 오검출 (False Positive) 또는 누락 (False Negative) 이 빈번하게 발생합니다.

2. 방법론 (Methodology: NESA)

저자들은 NESA (Neuro-Symbolic Static Program Analysis) 라는 새로운 프레임워크를 제안합니다. 이는 LLM 의 의미론적 이해 능력과 전통적인 파싱 기반의 결정론적 분석을 결합한 관계형 신경 - 심볼릭 (Relational Neuro-Symbolic) 접근법입니다.

핵심 아이디어

1. 문제 분해 (Problem Decomposition): 복잡한 분석 문제를 더 작은 하위 문제 (서브 - 문제) 로 분해합니다.
   • 구문적 속성 (Syntactic Properties): AST(추상 구문 트리) 파싱을 통해 결정론적으로 해결 (할루시네이션 제거).
   • 의미론적 속성 (Semantic Properties): LLM 프롬프팅을 통해 해결 (할루시네이션 위험 존재).
2. 분석 정책 언어 (Analysis Policy Language): 제한된 형태의 Datalog를 사용하여 분석 로직을 정의합니다.
   • 상징적 관계 (Symbolic Relations): 파싱을 통해 추출된 구문 정보 (예: 함수 인자, 행 번호, 제어 의존성).
   • 신경 관계 (Neural Relations): LLM 프롬프팅을 통해 추론된 의미 정보 (예: 데이터 의존성, 오염 전파).
   • 내재적 관계 (Intensional Relations): 최종 분석 목표 (예: 슬라이스 결과, 버그 탐지).

기술적 혁신: 할루시네이션 완화 전략

LLM 의 할루시네이션을 줄이고 효율성을 높이기 위해 두 가지 핵심 전략을 도입했습니다.

1. 지연 프롬프팅 (Lazy Prompting):

   • 신경 관계 (LLM 이 추론해야 하는 부분) 를 채우기 전에, 먼저 상징적 관계 (파싱 결과) 의 내용을 확정합니다.
   • 이를 통해 LLM 에게 프롬프트를 보낼 때 범위 (Scope) 가 제한된 특정 표현식만 대상으로 하여, LLM 이 추론해야 할 문제의 복잡도를 낮추고 할루시네이션을 최소화합니다.
   • 예: "모든 데이터 의존성 찾기" 대신 "특정 변수 $X$와 관련된 데이터 의존성 찾기"로 프롬프트를 구체화합니다.

2. 증분 프롬프팅 (Incremental Prompting):

   • Datalog 규칙 평가 과정에서 동일한 튜플 (Tuple) 에 대해 반복적으로 LLM 을 호출하는 것을 방지합니다.
   • 이미 LLM 을 통해 생성된 신경 관계의 튜플을 저장하고, 새로운 평가 단계에서 이를 재사용하거나, 새로운 튜플만 생성하도록 하여 토큰 비용과 시간을 절감합니다.

3. 주요 기여 (Key Contributions)

• 컴파일 없는 커스터마이징 가능한 분석 프레임워크: 사용자가 자연어 정의와 예시 (Few-shot examples) 만으로 Datalog 기반의 분석 정책을 작성할 수 있게 하여, 컴파일러 내부 지식 없이도 다양한 분석 작업을 수행 가능하게 함.
• 할루시네이션 완화 전략: 지연 프롬프팅과 증분 프롬프팅을 통해 LLM 의 오류를 체계적으로 줄이고 분석 성능을 극대화하는 평가 프로세스 제안.
• 광범위한 실험 및 검증: 프로그램 슬라이싱, 다양한 버그 유형 탐지 (XSS, DBZ, NPD 등), 실제 악성코드 및 오픈소스 프로젝트에서의 성능을 입증.

4. 실험 결과 (Results)

NESA 는 프로그램 슬라이싱과 버그 탐지 (Juliet Test Suite, TaintBench, 실제 프로젝트) 에서 기존 기법들과 비교하여 우수한 성능을 보였습니다.

• 프로그램 슬라이싱:
  • 정밀도 (Precision): 91.50%, 재현율 (Recall): 84.61%, F1 점수: 0.88.
  • 기존 최첨단 학습 기반 슬라이서 (NS-Slicer) 보다 F1 점수에서 0.06 포인트 향상.
• 버그 탐지 (Juliet Test Suite):
  • XSS(크로스 사이트 스크립팅) 탐지: 정밀도 98.95%, 재현율 94.00%.
  • APT(경로 이동), NPD(널 포인터 역참조) 등 다양한 버그 유형에서 높은 성능 유지.
  • 단순 프롬프팅 기반 (Few-shot CoT) 방법론들 (GPT-3.5, GPT-4 등) 보다 정밀도와 재현율 모두에서 월등히 우수함.
• 실제 프로젝트 적용 (TaintBench 및 메모리 누수):
  • TaintBench (악성코드): 오염 취약점 탐지에서 정밀도 66.27%, 재현율 78.57% 달성. 산업용 도구보다 F1 점수 0.20 포인트 높음.
  • 실제 메모리 누수: Uber 의 h3 라이브러리 및 dynamips 프로젝트에서 13 개의 실제 메모리 누수 버그를 발견하여 개발자가 수정함.
  • 비용 효율성: 버그 하나를 발견하는 데 드는 비용 (Cost-per-Recall) 이 기존 LLM 기반 방법론보다 낮음.

5. 의의 및 결론 (Significance)

• 실용성 증대: 컴파일 과정 없이도 불완전한 코드에서 분석이 가능하여, 현대적인 개발 워크플로우 (IDE, CI/CD) 에 분석 도구를 쉽게 통합할 수 있게 함.
• 접근성 향상: 복잡한 분석 엔진 구현 없이 자연어와 간단한 예시만으로 분석 로직을 커스터마이징할 수 있어, 비전문가도 정적 분석을 활용할 수 있는 장벽을 낮춤.
• 신뢰성 확보: LLM 의 무작위성과 할루시네이션을 심볼릭 분석 (파싱) 으로 제어하여, 정적 분석이 요구하는 높은 신뢰도를 확보하면서도 LLM 의 유연성을 살린 균형 잡힌 하이브리드 접근법을 제시함.

이 논문은 LLM 과 심볼릭 분석의 융합을 통해 정적 프로그램 분석의 새로운 패러다임을 제시하며, 실제 소프트웨어 공학 현장에서의 적용 가능성을 크게 높였다는 점에서 의의가 큽니다.