Detail View

이 논문에서는 데이터 기반 프로그램 분석에서 자동으로 피쳐(feature)를 생성해내는 기술을 제
시한다. 데이터 기반 프로그램 분석은 우리 주변에 널리 존재하는 코드베이스로부터 비용 효율적인
요약을 찾아내는 휴리스틱을 자동으로 학습하는 접근 방식을 말한다. 이러한 접근법들이 근래 들어
개발되어 분석기 설계자의 부담을 상당히 줄여주고 있지만, 자동화된 학습에 필요한 피쳐를 여전히
설계자가 직접 고안해내야 함을 요구하기 때문에 설계자는 여전히 고된 작업에서 자유롭지 못하다는
문제가 있다. 우리가 제시하는 기술은 이 피쳐 생성 단계를 자동화하는 것을 목표로 한다. 핵심
아이디어는 프로그램의 핵심 부분만 간추려내고 이를 일반화된 형태로 표현하여 피쳐로 사용하는
것이다. 우리 방식은 프로그램과 쿼리 튜플을 받아 해당 프로그램을 수 라인의 작은 프로그램으로
줄여내고 이를 일반화해내는데, 이 때 원래 프로그램과 줄여진 프로그램에 있어 쿼리에 대한 최종 증명
결과가 동일하다는 조건을 항상 유지하도록 한다. 생성된 각각의 작은 프로그램은 프로그램과 쿼리
튜플에 대한 불리안(Boolean) 피쳐로 사용이 되는데, 새로운 튜플이 주어졌을 때 이 작은 프로그램이
새로운 프로그램에 포함되면 우리는 새롭게 주어진 튜플이 해당 피쳐를 가진다고 판단한다. 우리는
이 기술을 세 종류의 분석에 적용했으며, 자동으로 생성된 피쳐에 기반한 분석들이 비용효율적임과
동시에 다양한 프로그램에 대해 성능의 편차 없이 잘 동작함을 실험적으로 보였다.

We present a technique for automatically generating features for data-driven program
analyses. Recently data-driven approaches for building a program analysis have been
developed, which mine existing codebases and automatically learn heuristics for finding a
cost-effective abstraction for a given analysis task. Such approaches reduce the burden of
the analysis designers, but they do not remove it completely; they still leave the nontrivial
task of designing so called features to the hands of the designers. Our technique aims
at automating this feature design process. The idea is to use programs as features after
reducing and abstracting them. Our technique goes through selected program-query pairs
in codebases, and it reduces and abstracts the program in each pair to a few lines of code,
while ensuring that the analysis behaves similarly for the original and the new programs
with respect to the query. Each reduced program serves as a boolean feature for program-
query pairs. This feature evaluates to true for a given program-query pair when (as
a program) it is included in the program part of the pair. We have implemented our
approach for three real-world static analyses. The experimental results show that these
analyses with automatically-generated features are cost-effective and consistently perform
well on a wide range of programs.

Abstract
국문초록
Contents
1 Introduction 1
2 Overview 4
2.1 Learning a Classifier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Automatic Feature Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.1 Feature Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.2 Matching Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3 Setting 10
4 Learning an Analysis Heuristic 11
5 Automatic Feature Generation 13
5.1 Generation of Feature Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.2 Transformation to Abstract Data-Flow Graphs . . . . . . . . . . . . . . . . . . . . 17
5.3 Abstract Data-flow Graphs and Queries . . . . . . . . . . . . . . . . . . . . . . . . 19
5.4 Final Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
6 Instance Analyses 23
7 Experiments 25
7.1 Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
7.2 Effectiveness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
7.3 Comparison with Manually-Crafted Features . . . . . . . . . . . . . . . . . . . . . 28
7.4 Impact of Reducing and Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
7.5 Generated Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
7.6 Caveats and Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
8 Related Work and Discussion 33
9 Future Directions and Conclusion 36
Bibliography 38
Acknowledgement