Analysis and Testing of Programs with Exception-Handling Constructs Saurabh Sinha and Jean Harrold Sookmyung Women’s Univ. PSLAB Ohe, hee jeong

1. Introduction Motivation Contribution Many software-engineering tasks require information about the control flow, control dependence, and data dependence among statements in a program analysis techniques should account for the effects of exception-handling constructs Contribution Effects of exception-handling constructs on several analysis Control flow analysis Control dependency analysis 많은 소프트웨어 엔지니어링 task들은 프로그램의 statement 사이에서 control flow, data flow, control dependence에 대한 정보를 필요로 한다. 기존의 연구에서는 이러한 분석 기술에 exception-handling constructs가 미치는 영향에 대한 고려가 이루어지지 않았다. 만약 이러한 exception-handling에 대한 고려가 이루어지지 않는다면 분석 기술들은 잘못된 정보를 산출하게 될 것이다

2. Exception in Java Exception is an object derived from the class java.lang.Throwable Throw statement variable, method call, new instance expression Exception criteria Non-resumable model of exception handing A java exception can be propagated up on the call stack Exception은 java.lang.throwable 클래스로부터 파생된 class의 instance이다. Exception의 throw statement에서 는 변수, 메소드 호출 또는 새로운 인스턴스를 통해서 발생하게 된다. Exception-handling 구조는 그림과 같이 exceptoin을 발생시키는 try 구문, 발생한 exception에 대해 처리해주는 chatch구문, 마지막으로 무조건 실행이 되야 하는 finally 구문으로 구성되어있다. Exception이 처리된 후에 control이 exception이 발생한 곳으로 돌아오지 않습니다. Exception이 발생한 method에서 exception이 처리되지 않는다면 그 메소드의 caller에게 그 exception이 전달되게 됩니다.

3. Effects of Exception-handling Constructs on Analysis Techniques

Exception-handling constructs Belong to a class of structure that cause arbitrary interprocedural control flow Interprocedural contorl Jump statement, halt statement Common effect Control may not return from the called procedure back to the call site Affect the flow of control across procedure Exception handling constructs는 interprocedural control flow 에 속하는것으로 jump statement나 halt statement 와 비슷하게 control flow에 영향을 미친다. 이러한 개념들은 procedures를 가로질러서 컨트롤의 흐름에 영향을 준다. 따라서 control-flow analysis로 부터 파생된 모든 analyses에 영향을 미친다.

Main() Insert () : 동전을 제대로 넣엇는지에 대한 고려 Vend() : 사용자의 선택을 받는다. Dispense() 를 호출 Dispense() : 올마른 item이 선택되었는지 조사하기 위해 여러 에러사항들을 체크한다.

3.1 The Vending-Machine program

3.2 Effects of Exception on analysis techniques Control flow analysis incorporate the exception-induced control flow influence control flow not only within a method, but across methods Data flow analysis Definition-use pair may not be detected the pair Exception-handling constructs introduce additional definition-use pairs in a program through the exception object. Data dependence analysis Consider the presence of potentially non-returning call site (PNRCs) Necessitate the computation of interprocedural control dependence <data flow> Control flow를 이용하여 data fact를 반복적으로 계산 예> 42번 statement에서 vm이 정의되었고 53번 구문에서 vm이 사용되었다. 이 definition-use pair는 만약 7번 구문에서 51번으로 가는 exceptional control flow가 control flow에 의해 만들어지지 않았다면 이 DUP는 발견되지 않는다. 38번의 오브젝트 e는 exception이 발생하면 55번에서 i와 같은 추가적인 definition-use pair가 생성된다.

4. Analysis Techniques to Accommodate Exception-Handling Constructs

4. 1 Control-Flow Analysis exception-handling constructs The intraprocedural control-flow The interprocedural control-flow Control flow analysis에서 exception handling constructs는 method를 가로질러 컨트롤 플로우가 발생한다. 따라서 intraprocedural control flow와 interprocedural control flow 모두를 고려해야 한다.

4.1.1 Intraprocedural analysis Try block에서 exception이 발생하면 exceptoin을 핸들링해줄 catch 구문으로 컨트롤이 이동 핸들러 코드의 실행 다음에는 일반적인 exceution은 exception이 처리되어진 try statement 다음에 오는 첫 구문이 실행된다. 컨트롤이 try statement를 빠져나가기 전에 finally block이 실행되고 exception이 처리 되지 않았어도 컨트롤은 try 구문을 빠져나간다. (5,3 12) try 발생 ->catch가 exception 핸들링 -> 하지만 또다른 exception이 발생. -> finally 블록은 exception 발생하지 않았다. (13,14,15) nested try statement (13, 6,11) 중첩된 try 구문이 exception을 전달하고 전달된 exception이 catch에서 처리되며 finally block 에서 또다른 exception 발생 두가지 종류의 finally Normal의 경우는 try 구문의 마지막에 도착하거나 catch 구문을 통해 빠져나가거나, 아니면 unconditional transfer statement (break, continue, return)로 인해 빠져나가는경우 Exception context는 exception이 try statement에서 핸들링 되지 못했을경우 <Intraprocedure control flow in java exception-handling constructs>

4. 1.1 Intraprocedural analysis 1. Exception-handling construct를 표현하기 위해서 기존의 CFG를 이용한다. 단 각 노드는 throw, catch, finally 블록이고 각각의 edge는 norm미 혹은 exceptional control flow 이다. Thrown node는 여러 개의 상속 노드들이 있고 각각은 throw 구문에 대응되는 exception의 type에 의해 결정된다. (40) 각각의 edge에는 label이 붙어있다. 2.Exception이 발생했는데 그것이 핸들링 되지 않는다면 그 exception은 전달-> exceptional-exit method들은 그 메소드에서 직접 발생한 exception이나 호출된 메소드에 의해서 간접적으로 발생된 exception을 전달한다. 예를 들어 vend()는 3개의 직접적으로 발생한 exception이 (IS, SNA, ZV)이 존재하므로 3개의 exceptional-exit가 있다. 또한 vend()에는 간접적으로 일어난 exception은 dispense를 호출함으로 인해 발생한 IA는 간접 호출 (38번) Incommig edge가 없는 노드들은 (22, 28)은 interprocedural representation

4.1.1 Intraprocedural analysis Step1 : throw의 outgoing edge가 없는 불완전한 CFG를 그린다. (abstract syntax tree나 java bytecode이용) Step2: 불완전한 CFG를 이용해서 throw statement의 잠재적인 exception 타입을 결정하기 위해 type inferencing을 수행한다. 마지막으로 outgoing edge를 throw노드에 추가시킨다. 필요한 exceptional-exit 노드와 exceptional context 상에서의 finally block의 실행을 표현하는 노드를 추가한다.

4.1.2 Interprocedural analysis Interprocedural control-flow graph Program P consists of CFGs for each method or procedure in P call node ---> connected to the entry node of the called method by a call edge exit node ---> connected to the corresponding return node by a return edge Call 에지와 called 에지의 엔트리 node를 연결 Called node와 리턴 노드를 연결

4.1.2 Interprocedural analysis ICFG Call edge와 return edge 총 4가지의 return edge가 있다. Exception이 발생하지 않아서 control이 calㅣ site 다음으로 오는 경우 Exception이 발생 했지만 try 구문에서 catch 되는 경우 Exception이 발생하였으나 해당 try 문에서 해결되지 않고 exception-exit가 있는 경우 위의 어떤 경우도 해당하지 않고 exception의 핸들링을 찾기 위해 A의 caller에게 전달

각 노드에 call 노드와 called 노드를 연결하는 call edge, return edge가 존재 Insert에서 illegarcoinexception이 발생 -> 51번에서 처리

4.1.2 Interprocedural analysis N을 call한 M, 먼저 calㅣ and return edge를 생성 N에의해 불려진 exceptoin type은 M에서 간접적으로 발생한 것이므로 M의 CFG에 finally block과 exceptiona-exit노드를 추가 만약에 M의 CFG에 exceptoinal-exit를 추가한다면 모든 M의 caller는 reprocess되야 한다.

4.1.3 Type inferencing for exception types The CFG construction requires information about exception types that can be raised at throw statements. Recent work uses points-to analysis to infer types in programs that contain exception-handling constructs Only consider the variables or method call CFG construction은 Exception type 에 대한 정보가 필요한데, 타입 inference의 정확성은 control flow representation에 잘못된 path 가 추가되지 않도록 하는것이다 Type-inference는 모든 throw statement에 발생하는것은 아니다 Throw가 새로운 instance를 발생하면 추론 필요 없고 variable이나 method call 인 경우만 고려

4.1.3 Type inferencing for exception types Four inexpensive approaches Conservative approximation Intraprocedural flow-sensitive analysis Interprocedural flow-insensitive analysis Combination of the intraprocedural flow-sensitive and the interprocedural flow-insensitive analysis Class내의 모든 subtype exceptionemf을 고려 exception이 varable에 의해 발생된것들중 strow statement에서 시작한다. 만 거꾸로 path를 따라간다. 최소한의 예측값을 결정해놓고 object-creation과 return 모든 라이브러리 호출의 리턴 파입을 통해 예측값들을 정재해 나간다. Flow sensitive analysis를 통해 결과를 내면 정확성을 높이기 위해서 flow-insensitive analysis를 해준다.

4.2 Control-Dependence Analysis The interprocedural control-dependence algorithm computes statement-based control dependences without constructing an IIFG Phase 1 identifies PNRCs that are caused by throw statement and halt statement Uses this information to compute partial control dependences Phase 2 Use partial control dependences to compute statement-based interprocedural control dependences

4.2.1 Computation of partial control dependency Phase 1 : identifies call sites that are PNRCs Step1 : for each call site, computes the set of nodes to which control can return following the call site Step 2 : constructs an augmented control-flow graph that summarized the effects of external control dependences on statements in a method. 1. 각각의 calㅣ site에 대해서 calㅣ site 다음에 control이 return 되는 노드들을 찾는다 만약 컨트롤이 지정되어있는 리턴 노드로 돌아오지 않고 다른 노드들에게 간다면 이 call site는 PNRC이다. 이러한 call site는 calㅣsite 뒤에 나오는 statement들의 컨트 롤 디펜던시에 영향을 주게 된다.

4.2.1 Computation of partial control dependency Partial control dependence Intraprocedural control dependences that are computed by applying a traditional technique for computing control dependence to the ACFG The partial control dependences for nodes that are control dependent on predicates in called methods contain a return-predicate node Partial control dependece는 control dependence를 구하는 기존의 방법을 ACFG에 적용하여 계산된 intraprocedural control dependences이다. Control이l 불려진 메소드내의 predicate에 의해 종속적인 노드들을 위해 partial control dependences들은 return-predicate node 를 갖는다. 예를 들어 17b같은경우는 return-predicate 노드인 rp17b를 갖게 되는데 왜냐면 17b의 컨트롤은 dispense() 메소드의 39번 statement 안의 predicate에 따라서 컨트롤이 dependence된다.

4.2.1 Computation of partial control dependency 예) vend() 메소드의 ACFG RP17b, RP21b는 return-predicate node 17번과 21번은 PNRC이므로 RP17b는 3개의 outgoing edge들이 있는데 각각 return site들과 연결 Return-predicate node : PNRC와 대응하여 return될 site의 에지를 가지고 있다 Super exit : 모든 M으로 부터의 exit 17b의 경우 dispens의 39번 문장이 컨트롤 디펜던스 하므로 RP17B는 return-predicate 노드

4.2.2 computation of interprocedural control dependences Partial control dependences Contain placeholder nodes-representing entry or return predicates-must be adjusted To compute interprocedural control dependences, phase 2 constructs an interprocedural representation of the program by connecting the ACFGs using call, return, and exceptional-return edges

4.2.2 computation of interprocedural control dependences Dispalys the graph constructed during Phase 2 of the control-dependence computation 각각의 노드에서 computation은 starting node에서부터 모든 패스를 거꾸로 따라서 graph를 이동하면서 노드와 연결가능한 가장 가까운 predicate를 찾는다. 예) 20번 노드 -> (39, exit) 이므로 20의 control dependece는 (39,F) 23번 노드는 IS와 SNA에지로부터 40번이 이어진다. 따라서 23의 control-dependence는 (40,IS) (40,SNA)이다. 27번 노드는 (24,F)