프로그램 분석의 구현.

Presentation on theme: "프로그램 분석의 구현."— Presentation transcript:

1 프로그램 분석의 구현

2 정적 분석 구현을 위한 도구 Java를 위한 정적 분석 틀(framework) 프로그램 분석기 생성기 Vortex Barat
BANE set-constraint analyzer generator Z/Z1/Z2 Abstract interpreter generator

3 Barat Java 언어를 위한 전단부(front-end) 설치 Java 프로그램의 정적 분석기 구현을 지원
소스 코드 및 실행 화일 이용 가능

4 Barat 역할 Abstract Syntax Tree(AST) 구성 이름 분석 및 타입 분석 AST 횡단(traversal)

5 AST 구성 자동 AST 구성 패키지 barat.Barat Barat의 진입점
메소드 getClass()와 getInterface()는 해당 AST node를 반환한다.

6 예제 public class FirstExample {
public static void main(String[] args) { barat.reflect.Class c = barat.Barat.getClass(args[0]); System.out.println("accessible fields of class "+ c.getName()); for(barat.collections.FieldIterator i=c.getFields().iterator(); i.hasNext();) { barat.reflect.Field f = i.next(); if(!f.isPrivate()) System.out.println("\t" + f.getType() + " "+ f.getName()); }

7 관련 패키지 패키지 barat.reflect 패키지 barat.collections AST의 노드 타입들을 포함하고 있다
Class, Interface, AbstractMethod, Field, Parameter, Block, ObjectAllocation 등 패키지 barat.collections AST 노드 타입 객체들을 위한 iterator들을 포함한다.

8 AST 노드 Type nodes Structural nodes Expression nodes Statement nodes
타입(Primitive or Reference Type)을 위한 노드 Structural nodes 사용자-정의 타입(클래스 혹은 인터페이스)의 내부 구조를 위한 노드 Expression nodes 식을 위한 노드 Statement nodes 문장을 위한 노드

9 interface Node public interface Node {
// container and containment aspect for this node public Object container(); public String aspect(); // helper methods for traversing the container chain public Object containing(java.lang.Class ofClass); public barat.reflect.Class containingClass(); public barat.reflect.AUserType containingUserType(); public barat.reflect.AMethod containingMethod() public int line_number(); // line number for a node: public boolean hasTag(String t); // access to tags (/*:special*/ comments): public barat.collections.StringList getTags(); public void accept (Visitor v); // method that calls back a visitor object: // defining attributes and retrieving attribute values: public void addAttribute(Object key, AbstractAttribute a); public Object attributeValue(Object key); }

10 Type nodes

11 Structural nodes

12 Expression nodes

13 Statement Nodes

14 Name Analysis 사용된 이름의 해당 선언을 찾아 준다. 식에서 필드 이름 사용 extends에서 클래스 이름 사용
레이블 이름

15 Type Analysis 각 Aexression의 타입을 자동 분석 타입 분석 결과
모든 Aexpression에 대해서 메소드 type()을 호출한다.

16 Java 프로그램의 AST 얻기 barat.reflect.Class c = barat.Barat.getClass("java.lang.Object");

17 AST 순회 Visitor 패턴을 기반으로 한 AST 순회 AST 노드와 방문 코드의 분리

18 Visitor 패턴 Visitor는 각 노드 A에 대해서 visitA(A o)를 구현
각 노드는 accept (Visitor v) 포함

19 Visitor 패턴 B C Barat.reflect class A { void accept(Visitor v) {
AST 노드 예> Barat.reflect class A { void accept(Visitor v) { v.visitA(this); } class B { v.visitB(this); class C { v.visitC(this); Visitor AVisitor { visitA(A x) { (x의 Child)B.accept(this); (x의 Child)C.accept(this); } visitB(B x) { … visitC(C x) { ... ① ② ③ ④

20 Barat이 제공하는 Visitor DescendingVisitor OutputVisitor DefaultVisitor
Depth-first visitor OutputVisitor Depth-first visit Output source code DefaultVisitor 모든 visit 메소드를 빈 메소드로 구현 일부 AST 노드만을 방문할 때 유용

21 DescendingVisitor 예: visitClass( ) public void visitClass (Class o) {
for (ConstructorIterator i=o.getConstructors().iterator();i.hasNext();) { i.next().accept (this); } for (FieldIterator i = o.getFields().iterator(); i.hasNext();) { for(ConcreteMethodIteratori=o.getConcreteMethods().iterator();i.hasNext();) {

22 Visitor 만들기 방문 노드 XXX에서 하고자 하는 일을 visitXXX()에서 재정의한다.
예: java.lang.System.out 접근 빈도 조사 public class MyVisitor extends barat.DescendingVisitor { public int result = 0; public void visitStaticFieldAccess (StaticFieldAccess o) { Field f = o.getField(); if (f.qualifiedName().equals ("java.lang.System.out")) result++; super.visitStaticFieldAccess (o); }

23 Visitor 사용 barat.reflect.Class c = barat.Barat.getClass("example.MyClass"); MyVisitor v = new MyVisitor(); c.accept (v); System.out.println ("Result: " + v.result);

24 Attribute 사용 각 노드에 데이터 저장 및 검색 가능 Attribute 객체 저장
n.addAttribute(k, a) where k is a key attributeValue(k) Attribute 객체 저장 두 종류의 Attribute 객체 제공 ConstantAttribute CachedAttribute

25 ConstantAttribute 객체 o를 저장 저장된 객체 o를 반환
n.addAttribute(k, new ConstantAttribute(o)); 저장된 객체 o를 반환 n.attributeValue(k);

26 CachedAttribute calculate() 메소드에 의해 계산된 값을 저장 계산된 값이 있으면 사용하고 없으면 값 계산
c.addAttribute(key, new CachedAttribute() { protected Object calculate() { … return result; } )

27

28 Barat 이용 사례 1 정적 분석 2 단계로 구성 예외 분석(Uncaught exception analysis)
각 메쏘드의 처리되지 않는 예외들을 분석한다. 2 단계로 구성 집합 관계식(set-constraint) 구성 예외 관련 노드들에 대해서 집합 관계식 해답 구하기(solving) Repeat-until no change

29 Barat 이용 사례 2 프로그램 변환을 이용한 실행 정보 제공 event 발생 및 처리 과정 추적
exception 발생 및 처리 과정 추적 thread 생성 및 진행 과정 추적

30 프로그램 변환 + Barat Java Program P Java Program P’ AST Java Program P’
Transformer Java Program P Java Program P’ AST Java Program P’ Input Output + Trace정보 Profile정보 실행 정보

31 예외 발생 및 처리

32 숙제 #3 Java 프로그램의 각 클래스에 대해서 다음을 프린트한다. 클래스 이름 필드 변수 생성자 헤더 메소드 헤더
부모 클래스 구현한 인터페이스들의 집합