Combining Static Code Analysis and Large Language Models Improves Correctness and Performance of Algorithm Recognition

논문 요약: 정적 코드 분석과 대규모 언어 모델 (LLM) 의 결합을 통한 알고리즘 인식의 정확성 및 성능 향상

1. 연구 배경 및 문제 정의 (Problem)

• 배경: 개발자들은 업무 시간의 상당 부분을 소스 코드 이해 (Program Comprehension) 에 할애합니다. 소스 코드 내의 알고리즘을 자동으로 식별하는 능력은 프로그램 이해, 유지보수, 소프트웨어 품질 향상에 중요한 기회를 제공합니다.
• 문제: 기존 알고리즘 인식 기술은 검색 패턴 (정규식 등) 이나 머신러닝 분류기에 의존해 왔으나, 최근 LLM 이 코드 관련 작업에서 뛰어난 성능을 보임에도 불구하고, LLM 만을 단독으로 사용할 경우 다음과 같은 한계가 존재합니다.
  • 높은 실행 시간 (Runtime): LLM 호출 비용과 시간이 매우 큽니다.
  • 과도한 이름 의존성: 식별자 (Identifier) 이름에 지나치게 의존하여, 이름이 모호하거나 난독화된 경우 성능이 저하될 수 있습니다.
  • 정확도 vs 효율성 트레이드오프: 복잡한 프롬프트는 성능을 높이지만 실행 시간을 증가시킵니다.

2. 연구 방법론 (Methodology)

이 연구는 실세계 오픈소스 자바 (Java) 코드를 기반으로 한 BigCloneEval (BCEval) 데이터셋을 사용하여 다음과 같은 실험을 수행했습니다.

• 평가 대상 모델: GPT-4o mini, Llama 3.1 70B Instruct, Mixtral 8x22B Instruct 등 최신 LLM 3 종을 사용했습니다.
• 연구 질문 (RQ) 및 접근 방식:
  • RQ1 (프롬프트 전략): 다양한 프롬프트 전략 (Yes/No, 점수 매기기, In-Context Learning, Chain-of-Thought) 이 알고리즘 인식 성능과 실행 시간에 미치는 영향을 분석했습니다. 특히, **In-Context Learning (ICL)**에서 양 (+) 과 음 (-) 예제의 조합과 개수를 변형하여 최적의 설정을 찾았습니다.
  • RQ2 (정적 분석과의 결합): LLM 호출 전, **정적 코드 분석 (Static Code Analysis)**을 통해 불필요한 메서드를 선별 (Filtering) 하는 필터 패턴을 도입했습니다.
    • 키워드 기반 필터: 식별자 이름 (예: sort, bubble) 을 정규식으로 매칭.
    • 구조적 필터: AST(추상 구문 트리) 기반의 DSL 을 사용하여 알고리즘의 핵심 구조 (예: 중첩 루프, 배열 접근 패턴) 를 매칭.
    • 이 필터들은 LLM 에게 전달될 메서드 수를 줄여 실행 시간을 단축하고, LLM 이 처리할 데이터의 품질을 높여 정확도를 개선하는 것을 목표로 했습니다.
  • RQ3 (이름 정보 의존성): 식별자를 무작위로 난독화 (Obfuscation) 하여 LLM 이 이름 정보에 얼마나 의존하는지, 그리고 의미론적 (Semantic) 분석이 가능한지 검증했습니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

1) 프롬프트 전략 최적화 (RQ1)

• In-Context Learning (ICL) 의 효과: Baseline 대비 4~8%p의 F1-Score 향상을 보였습니다.
• 최적의 설정: 2 개의 양 (+) 예제만 제공하는 것 (2P+0N) 이 성능과 실행 시간 간의 가장 좋은 균형 ("Sweet-spot") 을 이루었습니다. 4 개의 양/음 예제 (4P+4N) 는 성능을 약간 더 높였지만 실행 시간은 2 배 이상 증가시켰습니다.
• Chain-of-Thought (CoT): CoT 는 실행 시간을 급격히 증가시켰음 (약 15~65 배) 에도 불구하고, ICL 보다 낮은 성능을 보여 비효율적인 것으로 판명되었습니다.

2) 정적 분석과 LLM 의 하이브리드 접근 (RQ2)

• 실행 시간 획기적 단축: 필터 패턴을 적용하여 LLM 호출 횟수를 **72.39% ~ 97.50%**까지 감소시켰습니다.
• 성능 향상: 필터링을 거친 후 LLM 에게 전달된 데이터는 정밀도 (Precision) 가 높은 데이터이므로, LLM 의 오분류가 줄어들어 F1-Score 가 최대 12%p 까지 향상되었습니다.
  • 예: "Prominent Feature" 패턴과 LLM 을 결합했을 때, LLM 단독보다 정밀도와 F1-Score 가 모두 개선되었습니다.
• 결론: 정적 분석 필터는 LLM 의 단점 (높은 비용) 을 보완하고 장점을 극대화하는 효과적인 전처리 단계입니다.

3) 이름 정보 의존성 분석 (RQ3)

• 난독화 실험 결과: 식별자 이름을 무작위로 변경했을 때, LLM 의 Recall(재현율) 은 4~5%p 감소했으나, Precision(정밀도) 은 5~17%p 증가했습니다.
• 전체 성능: 오히려 F1-Score 가 3~10%p 증가했습니다. 이는 LLM 이 단순히 이름에 의존하는 것이 아니라, 코드의 실제 의미론적 구조를 이해하고 있음을 시사합니다.
• 의미: LLM 은 이름 정보가 없어도 대부분의 알고리즘 구현을 식별할 수 있는 능력을 갖추고 있습니다.

4. 연구의 의의 및 결론 (Significance & Conclusion)

• 하이브리드 접근법의 가치: LLM 만을 사용하는 것이 아니라, 경량의 정적 코드 분석을 결합하는 것이 실행 시간을 대폭 줄이면서 동시에 정확도도 향상시키는 가장 효과적인 전략임을 입증했습니다.
• 실용적 적용: 이 기술은 코드 리뷰 자동화 (비효율적인 알고리즘 식별), 지적재산권 보호, 교육 도구 (학생 과제 피드백) 등 다양한 소프트웨어 공학 활동에 적용 가능합니다.
• 미래 작업: 자동화된 필터 패턴 생성 파이프라인 개발 및 IDE 플러그인 구현 등을 통해 개발자 워크플로우에 통합하는 방향이 제시되었습니다.

핵심 통찰:
이 논문은 대규모 언어 모델이 강력한 도구이지만, 단독 사용 시 비효율적일 수 있음을 지적하며, 전통적인 정적 분석 기법과 LLM 을 결합한 하이브리드 아키텍처가 알고리즘 인식 과제의 실용성과 효율성을 동시에 해결할 수 있음을 실증적으로 증명했습니다.