평가

현재 존재하는 Static Analysis 도구들 가운데, 가장 citation이 많은 논문이다. 현재 기준으로 2000개 남짓. IccTA랑 합쳐져서 성능도 다른 도구들 대비 나쁘지 않은 것으로 보인다(이전 포스팅 참고).

글을 굉장히 잘 썼다. 너무 과하게 자세하게 서술하지도 않으면서 적절한 정도의 깊이로,, (나는 자세히 설명하지만 다 알려주는 것은 아니고, 궁금하면 코드 보던가? 정도의 느낌) 그래서 애매하게 이해할 수 있고 살짝 찝찝한 느낌으로 끝나는 느낌이다.

모든 내용을 이해할 수는 없었다. 말 그대로 코드를 봐야할 것 같은 느낌이고, IFDS를 모르는 상황, 안드로이드 동작 원리를 정확히 다는 모르는 상황에서 이해하기는 쉬운 일은 아니었다. 그럼에도 도움이 많이 되었다.

특히 글 마지막에 본인의 한계를 명확히 평가하고 제시한 부분이 약간 쿨해보였다. 우리는 아주 멋~진 것을 가져왔는데 (꿀리는 게 없으니까) 한계도 다 보여줄게~ 이런 느낌.

근본있는 논문이고 배울 점도 많고, 알고리즘도 비교적 자세하고 알기 쉽게 설명해주니까 종종 와서 참고하면 좋을 것 같다.

0. Abstract

(깔끔한 서문.)
최근의 스마트폰은 비밀스러운 데이터들로 가득하다. 동시에 스마트폰 유저들은 실수로 중요한 데이터를 유출하는 부주의하게 설계된 앱들로 괴롭힘 당한다. 현존하는 static taint analysis 도구들이 이러한 데이터 유출을 빠르게 찾을 수 있는 가능성이 있지만, Android에 대한 접근들은 거친-알갱이의 근사치를 이용하는 것들이 많아, missed leak이나 false alarm 등이 많이 발생한다.
우리는 연구에서 FlowDroid를 공개한다, 안드로이드 애플리케이션에 대한 새롭고 매우 정확한 static taint analysis 도구. Android의 lifecycle에 대한 정확한 모델링이 Android framework에 의해 일어나는 callback들을 정확하게 다룰 수 있게 해준다. 한편 context, flow, field, object-sensitivity는 false alarm을 줄여준다. 새로운 알고리즘이 정확성과 효율성을 동시에 올려주었다.
우리는 DroidBencheh도 공개하였다, 안드로이드 앱에 대한 taint analysis의 효율성과 정확성을 테스트할 수 있는 오픈 소스 테스트 셋. 여러 벤치 및 잘 알려진 테스트 애플리케이션을 이용해 테스트를 진행하였고, FlowDroid는 굉장히 높은 부분의 data leak을 찾아내었다, false positive의 비율을 낮게 유지하면서도. DroidBench에서는 93%의 recall과 86%의 정확도를 달성하여, 다른 기존 도구를 크게 앞질렀다. Google Play의 500개의 앱과 VirusShare project의 1000개의 앱에서도 leaks를 성공적으로 발견하였다.

1. Introduction

[문제 제기(Privacy Leaks on Android application) - 챌린지 제시(1. lifecycle modeling, 2. system events handling callback, 3. aliasing and virtual constructs) - 해결 과정(In this work, Contributions)]
안드로이드 마켓 쉐어가 81%. 안드로이드 유저의 프라이버시 데이터가 공격 대상이 되고 있음. 안드로이드 malware에서의 주요한 위협은, 위치 정보, 연락처, 사진, SMS 등등 민감한 정보를 유출하는 개인정보 위반이다. 그러나 악의적이지 않고, 주의깊게 설계된 애플리케이션이라 할지라도 그러한 유출에서 고통받고 있다. 예를 들어 광고 앱 등이 있다. 이것은 수익 창출을 위해 넣는 것이지만, 그들의 보안적 함축이나, 그 라이브러리들이 어떤 데이터를 컨트롤하는지에 대해 잘 알지 못한다. 보통의 라이브러리들은 개인을 식별할 수 있는 정보들을 가져올 수 있다.
Taint analysis는 이러한 문제를 앱 분석, 악의적인 데이터흐름을 공개함으로써 해결하려 하였고, 그러한 정보를 분석가나, 자동화된 탐지 도구에 공개하도록 하려 한다. 이런 접근은 민감한 "tainted" 정보를 추적한다(미리 정의된 정보, 예. 위치정보를 반환하는 API). 주어진 sink를 만날 때 까지 추적한다(socket에 정보를 쓰는 함수).어떤 데이터가 어디로 유출되었는지에 대한 정보를 준다. 분석은 앱을 동적으로, 정적으로 조사할 수 있다. 그러나 동적 분석은, 코드커버리지를 위해 많은 테스트 런을 요구한다. 게다가 현재의 악성분석은 다이내믹 탐지기를 알고 있어, 회피가 가능하다.
정적 분석은 이러한 문제들을 공유하지는 않지만, 부정확성의 문제를 갖는다, 프로그램의 Inputs을 추상화해야하고, 런타임 오브젝트를 추측해야하기 때문이다. 런타임 실행에 대한 정확한 모델링을 하는 것이 특히 어려운 부분인데, 이러한 앱들은 stand-alone 애플리케이션이 아니라, Android framework 내부의 플러그인이기 때문이다. 앱은 별개의 lifecycle을 가지는 서로 다른 컴포넌트로 구성된다. 앱의 실행 동안, Android framework는 앱의 서로 다른 콜백을 호출하고, 시스템의 이벤트로서 알림을 주어, start/pause/resume/shutdown 할 수 있다. 앱의 제어 흐름을 예측하기 위해서는 static analysis는 컴포넌트의 lifecycle을 모델링해야 할 뿐만 아니라, system-event를 처리할 수 있는 콜백들을 통합해야 한다(GPS와 같은 센서 등). 콜백함수를 인식하는 것은 사소하지만 섬세한 알고리즘이 요구된다. 또다른 챌린지는 UI 내부의 민감한 정보로부터 온다. 각자의 컨텐츠를 반환하는 API는 프로그램 코드만으로 탐지되지 않는다. 대신, 그들의 탐지는 manifest와 XMl layout file에 저장된 보조적인 정보가 필요하다. 안드로이드 앱은 aliasing과 virtual dispacth construct도 가지고 있다. 전형적인 Java static analysis는 이러한 문제들을 어느정도의 context- and object-sensitivity를 통해 처리하였다. Android framework의 특징은 보통의 경우보다 처리하기에 어렵게 만들고, 따라서 우리는 deep aliasing relationships를 expose하는 방법을 선택하였다.
이전의 Android data-flow 분석들은 만족스럽지 않게 이러한 문제들을 처리하였다. 신뢰할만한 lifecylce 모델링 없이는 놓칠 수 있다. 더 나쁜 점은, over-approximation하여, false warning을 많이 생성한다. 보안 분석가로 하여금 툴 자체를 사용하기를 중단하게 만든다.

In this Work,

FlowDroid를 소개함. 앱의 바이트코드와 configuration을 분석하여 potential privacy leak을 탐지. 이전 연구에 대비하여, context flow field object-sensitive한 첫 static analysis 도구이다, Android lifecycle을 온전하게 모델링하면서, callback과 UI 위젯들을 정확히 처리하면서. 또한 on-demand alias 분석을 이용한다. 분석 알고리즘은 Andromeda로부터 영감을 받았다. 이 도구는 2013년부터 오픈소스로 존재하여, 몇몇 그룹으로부터 선택되었었다.
측정에 대한 필요가 있어 DroidBench도 만들었다 ..
FlowDroid는 조직 내에서 개발된 안드로이드 앱을 안전하게 하기 위해서, 혹은 악성 앱을 분류하기 위해서 사용될 수 있다. ... 로 측정해 보았을 때 93% 86%의 정확도가 나왔다 ...

Contribution

• FlowDroid, 안드로이드 lifecycle과 UI 위젯을 고려하는 첫 context field object flow-sensitive taint analysis 도구이다, 특히 정확한 on-demand alias 분석을 할 수 있다.
• 오픈소스 구현이다
• DroidBench라는 벤치마크 도구
• 기존 도구에 비해 압도적인 성능!
• Google Play에서 500개의 앱, VirusShare 프로젝트에서 1000개의 앱을 통한 실험.

2. Background and Example

motivating example을 들면서 이 연구에서 상정하고 있는 공격자 모델에서 이야기 하고자 한다. 예시에서 UI에 표시되는 activity를 구현하고 있다. 앱은 restart할 때마다 text field로부터 password를 읽고 있다. 유저가 버튼을 클릭하면, passsword는 SMS로 보내진다. password(source)가 SMS API(sink)로 이동하는 tainted data flow이다. sendMessage()가 app의 UI와 연결되어 있어, 유저가 버튼을 클릭할 때에 활성화 된다. 안드로이드에서 listener는 코드에 명시되어 있거나 layout XML 파일 내부에 존재하기도 한다. 따라서 코드만을 분석하는 것은 불충분하고, metadata 파일까지 분석해야 정확하다. 이 코드에서 onRestart()가 sendMessage()보다 먼저 실행되어야만 leak이 일어난다. false negatives를 피하기 위해 앱의 lifecycle을 정확하게 모델링할 필요가 있다, 유저가 앱 재실행 전에 버튼을 클릭할지도 모르는지 인식하여야 함.
false positives를 피하기 위해, 위 예시는 field-sensitive해야 한다. user 오브젝트는 name과 password를 가지지만, 오직 password만이 private하게 고려되어야 한다. Object-sensitivity는 (이 예시에서는 불필요하지만) 서로 다른 곳에서 할당되었지만 같은 코드 위치에 있을 때에 필요하다. 실험 과정에서 우리는 deep object sensitivity가 요구되는 몇몇 케이스를 발견했다. 이것은 상대적으로 깊은 호출과 할당 체인을 사용하는 Android framework 때문이다.
String concatenation은 이러한 연산을 통해 data가 어떻게 변화하는지를 정의할 수 있는 모델링이 필요하다. 이러한 연산을 일반 함수처럼 처리하는 것은 정확하지 않다.

Attacker model

FlowDroid는 데이터 플로우를 탐지할 때에 일반적으로 사용될 수 있다. 악의적인 사례들에 대해서는, 다음의 공격자 모델을 상정한다. 공격자는 임의의 악의적인 Dalvik bytecode를 삽입할 것이다. 일반적으로 공격자의 목표는 유저에 의해 부여된 방대한 권한을 이용하여 개인 정보를 유출하는 것이다. FlowDroid는 앱 인풋과 설치 환경에 대해서 온전한 가정을 하였는데, 공격자가 또한 그러한 것들을 함부로 변경할 수 있다는 것을 의미한다(?). 그러나 FlowDroid는 공격자가 Android platform의 보안 정책들을 우회할 수 없다고 가정하였고, side channel을 공격하지 않는다고 가정하였다. 나아가, 우리는 공격자가 data leak을 가장하기 위해 Implicit flows를 이용하지 않는다고 가정했다.

3. Precise Modeling of Lifecycle

Multiple entry points

[main 함수가 없고, 각 컴포넌트의 lifecycle에 따라 동작함. 이를 dummy main을 만들어서 해결하였음.]
안드로이드 애플리케이션은 main 함수가 없다. 앱은 대신 여러개의 entry points들을 갖는다. 안드로이드 운영체제는 애플리케이션 내의 모든 컴포넌트에 대해 온전한 lifecyle을 정의한다. 개발자가 정의할 수 있는 4개의 컴포넌트가 있다. activity는 유저 액션에만 집중하고, services는 백그라운드 작업을 수행하고, content providers는 데이터베이스 저장 관련을 하고, broadcast receivers는 글로벌 이벤트를 듣는다. 이러한 컴포넌트들은 미리 정의된 운영체제 클래스로부터 custom class를 끌어내어 구현한다, 그리고 그 결과들이 AndroidManifest.xml에 등록되어 lifecycle methods를 덮어쓴다. 안드로이드 시스템은 환경에 따라 이러한 method를 호출하여 start stop pause resume 을 한다. 메모리 고갈의 경우에는, 애플리케이션을 stop하였다가 나중에 restart할 수도 있다. 결과적으로 call graph를 구상할 때에 Android 분석은 단순하게 "main" method를 분석하는 방법으로 분석할 수 없다. 대신, Android lifecyle 내부의 모든 가능한 전환들이 정확하게 분석되어야 한다. 이러한 문제를 처리하기 위해 FlowDroid는 lifecycle을 에뮬레이팅하는 dummy main을 구축하였다.

Asynchronously executing components

[여러 개의 컴포넌트가 각각의 lifecycle을 갖는 것을 분석하기 위해서, 모든 가능한 순서를 고려함. IFDS를 이용하여 모든 경로를 탐색할 필요 없이 효율적으로 dummy main을 만들 수 있음(자세한 내용은 뒤에)]
앱은 여러 개의 컴포넌트를 가질 수 있다. 액티비티가 각각 실행되기는 하지만, 그들의 순서를 미리 예측할 수는 없다. 한 액티비티는 유저에 의해 처음 실행된 이후에 유저의 입력에 따라 다른 액티비티를 실행할 수 있다. 서비스는 백그라운드 작업을 병렬적으로 수행한다. FlowDroid는 모든 컴포넌트가 임의의 순서로 동작(반복을 포함)한다고 가정함으로써 컴포넌트의 실행을 모델링하였다. 어떤 정적 분석들은 path-sensitive라서, 가능한 프로그램 경로들을 각각 고려한다. 그러한 경우에 모든 가능한 순서를 고려하는 것은 매우 비용이 클 수 있다. FlowDroid는 IFDS에 기반하여 분석을 진행한다, IFDS는 path-sensitive 하지 않은 대신, control-flow merge point의 어떤 부분이든 분석 결과를 바로 합칠 수 있다. 따라서 FlowDroid는 개별적인 컴포넌트 lifecycle과 callback이 가능한 dummy main을 생성하고 효율적으로 분석할 수 있다. 모든 가능한 경로를 탐색할 필요가 없다.

Callbacks

[callback과 해당하는 컴포넌트를 연관지음. call graph를 그릴 때에 안드로이드 시스템 내부에서 callback을 찾고, 확장하고를 반복하여 생성됨. 비용이 크지만 더 정확하다고 함.]
안드로이드 운영체제는 애플리케이션이 위치 정보나 UI에 대한 다양한 callback을 등록할 수 있도록 한다. FlowDroid는 이러한 콜백을 dummy main 내부에 콜백을 모델링할 수 있도록 한다, 예를 들면 애플리케이션이 저장한 위치 정보를 콜백 함수에 파라미터로 넘겨 주었고, 이것을 액티비티가 종료된 후에 인터넷으로 전송하는 경우를 인식하기 위해서. callback 함수가 호출되는 순서는 예측할 수가 없는데, 따라서 FlowDroid는 모든 가능한 순서로 callback이 호출될 수 있다고 가정한다. 그러나 callback은 부모 컴포넌트가 실행될 때에만 호출될 수 있다. 정확성을 위해 컴포넌트와 그들이 등록한 callback을 연관지었다. 예를 들면 액티비티는 버튼이 눌렸을 때에 실행될 callback을 등록할 수 있다. 각각의 callback handler는 그러면 이 액티비티의 onResume()과 onPause() 사이에서 분석되어야 할 것이다.(A 액티비티의 함수가 B 액티비티에 callback으로 등록되어 있을 때, B 액티비티에서 callback이 실행되면, A 액티비티는 onResume() -> onPause()하게 되는데 이런 맥락에서 callback을 분석해야 한다는 뜻임)
callback handler를 등록하는 2가지 방법이 있다. 1) 액티비티의 XML 파일 내부에 선언될 수 있다. 2) 특정 시스템 함수에 잘 알려진 호출을 이용하여 부득이하게 등록될 수 있다(?). FlowDroid는 2가지를 모두 지원한다. 추가적으로 안드로이드 시스템 내부의 함수를 덮어쓰는 방법으로 공격자가 문서화되지 않은 callback을 등록하는 위험이 있다. FlowDroid는 이러한 덮어쓴 함수를 인식하는데, 버튼 클릭과 같은 보통의 callback handler처럼 다루면서.
애플리케이션 코드 내에 등록된 callback을 찾기 위해서, FlowDroid는 컴포넌트 별로 call graph를 계산한다, lifecycle 메소드로부터 시작하여. 이 call graph는 함수가 잘 알려진 callback interface 중 하나를 형식적인 파라미터로써 사용하는 안드로이드 시스템 함수를 찾는 데에 이용된다. 이후에 call graph는 이러한 새로 발견된 callback들을 포함하면서 확장되고, callback handler가 그들 자신의 새로운 callback을 등록할 수 있기 때문에 스캔이 다시 일어난다. 이런식으로 FlowDroid의 call graph는 고정 지점에 도달할 때까지 확장되고 계속 분석된다. 이러한 방법이 callback interface를 구현하는 class를 찾는 것보다 비용이 많이 소모되지만, 컴포넌트와 콜백 간의 더 정확한 분석을 할 수 있도록 해준다. false positive를 줄여주고, 이어지는 taint analysis에서의 시간을 효과적으로 줄여준다. dummy main이 만들어지기만 하면, 앱의 엔트리 포인트로부터 최종 call graph를 계산한다.
layout XML에 정의된 callback의 경우에는, 각각의 XML 파일이 하나 이상의 애플리케이션에 매핑된다. 버튼 클릭 핸들러는, 각각의 버튼을 가지고 있는 액티비티에 대해서만 유효하다. FlowDroid는 각각의 액티비티가 어떤 식별자를 XML 파일에 등록했는지를 분석한다. 이 정보는 매핑에 사용된다.

Example

최대의 정확성을 얻기 위해서, FlowDroid는 각 앱에 대해서 dummy main을 생성한다. 각각의 main method는 앱의 XMl 설정 파일에 따라 런타임에 실제로 일어날 수 있는 lifecycle의 일부분을 포함할 뿐이다. 사용 불가능한 액티비티들은 자동으로 필터링되고, callback 함수는 그들이 실제로 속한 컴포넌트의 context 속에서만 호출된다. 버튼 클릭 핸들러는 각각의 액티비티의 context에서만 분석된다. 위의 그림에서 dummy main 함수의 control-flow graph를 나타낸다. 그래프 모델은 sendMessage 콜백과 함께 확장되었다. p는 FlowDroid가 정적으로 평가할 수 없는 불투명한 추측을 의미한다. 따라서 분석은 p를 포함하여 진행된다.

4. Precise Flow-Sensitive Analysis

[aliasing 처리를 위해 개념을 Figure를 통해 설명하고, Section 4.1.과 4.2.에서 나누어 설명할 부분에 대해 목차를 잡아줌.]

object-sensitivity를 위해서는 aliasing을 효과적으로 처리해야 함. 위의 Figure을 보면, FlowDroid가 전방위 taint 분석과 on-demand backward-alias analysis를 결합하여 b.f.가 tainted 되었음을 분석한 것이다. 1) tainted 값인 w는 전방으로 전파되면서, x.f.(heap object)를 오염시킨다. 2) w와 x.f.에 대해서 taint 추적을 계속한다. 3) 중요한 부분이다. heap object가 tainted 되었을 때마다, backward analysis는 각각의 object의 alias를 위해서 윗 방향으로 검색한다. 7)에서는 alias인 b.f가 발견되고, 보통의 taint와 같이 전방위 탐색한다.
FlowDroid는 procedure 간의 부분적 전달 문제를 해결하기 위해 IFDS 프레임워크 내부에서 taint-analysis를 모델링하였다. Section 4.1.에서는 분석에서 사용하는 전달 함수에 대해 설명한다. 모든 함수는 상대적으로 표준화되어있다. 그러나 FlowDroid의 분석이 표준적인 taint-analysis 알고리즘과 다른 점은, tainted value가 heap(field나 array)에 할당되는 명령어 부분이다. 이러한 상황은 backward alias analysis를 야기하는데, Section 4.2.에서 더 자세히 설명한다. 공간 문제 때문에 flow function에 대해서는 설명 수준에서 끝낸다. 우리의 접근을 재현하고 싶은 사람들을 위해서는, Technical Report를 첨부한다.

4.1. Taint analysis

[access path의 개념과 transfer 함수의 동작 원리를 설명. transfer 함수는 우항이 taint되면 좌항을 taint시키고, array의 경우 일부만 taint되어도 전체를 taint함. 함수 호출 해석 시에 callee의 맥락에서 access path를 변환해서 판단하고, 리턴 시에는 다시 caller의 맥락으로 변경함]
forward, backward 분석은 access path를 통해 전파되는데, 이것은 x.f.g의 형태를 가진다. x는 로컬 변수 혹은 파라미터이고, f와 g는 필드이다. access path는 유저가 설정한 최대 길이에 따라 다른 길이를 가진다(디폴트는 5). 길이가 0인 경우에는 단순히 로컬 변수 혹은 파라미터이다. FlowDroid에서 access path는 이러한 경로를 통해 도달 가능한 모든 오브젝트의 집합을 의미한다. 예를 들어 x.f는 x.f.g, x.f.h, x.f.g.h 등등을 모두 포함한다.
할당을 위한 transfer 함수는 오른쪽 operand가 taint 되어 있다면, 왼쪽도 taint되었다고 판단한다. array에 대한 할당은 보수적으로 판단되어, 전체 array를 taint한다. x 변수에 대해 "new"를 이용하여 새롭게 할당하는 것은 x를 기반으로 모델링되었던 모든 access path를 삭제한다. 함수 호출은 callee의 맥락을 기반으로 access path를 해석한다, 실제 함수를 형식적인 파라미터로 변경하면서.(위의 예시에서 callee는 오른쪽의 foo ( z ) 부분이고, 실제 a 변수를 형식적인 z 파라미터로 변경하여 taint 분석을 한다는 뜻임) 정반대의 해석이 함수가 리턴될 때 일어나고, 리턴 값이 존재한다면 포함해서. (리턴될 때에는 z를 기준으로 분석되었던 것이 다시 a로 변환되어 해석된다는 뜻임) IFDS 기반의 보통 분석들 처럼, FlowDroid는 call-to-return 함수를 포함한다(caller 쪽의 method 호출을 무시한다). 이 함수는 호출과 관련 없는 taint를 탐색하고, source에서 새로운 taint를 생성하고, sink에서의 taint를 보고하고, native call에서의 taint를 탐색한다. 이건 Section 5에서 다시 설명~!

4.2. On-demand alias analysis

tainted 값이 필드나 어레이 같은 힙에 할당되었을 때, FlowDroid는 target variable의 alias를 위해 뒤로 검색을 하고, 그들 역시 taint한다. Listing 2에서 파라미터 in을 감염시키는 taintIt가 첫 번째 호출이라고 가정하자. 라인 10에서 x.f. 이것이 access path x.f를 감염시킨다, x.f = in이기 때문에. 이러한 상황에서(힙 감염), FlowDroidsms x.f에 대해 뒤로 검색을 실시하여, 라인 9에서 out.f를 발견한다. 여기에서 새로운 전방 탐색이 out.f로부터 실시되어 라인 11에서의 leak을 발견할 수 있다. 그럼에도 불구하고, 후방 탐색이 또다른 후방 탐색으로 이어질 수도 있는데, main 함수에서 p.f를 발견하고(이것도 후방탐색), 이것이 또다른 전방탐색을 만들어 라인 4의 leak을 탐지할 수 있다.

Maintaining context sensitivity

[forward, backward 분석이 잘 연계되어야 한다.]
알고리즘 1과 2는 forward, backward analysis solver의 메인 루프를 보여준다. 알고리즘은 독자가 IFDS 알고리즘 기술에 익숙하다고 전제한다(ㅠㅠ). 두 개의 solver는 그들의 worklist를 동작하면서, 현재의 상태/노드 n 까지의 계산된 data-flow를 요약하는 소위 path-edge를 포함시킨다. edge ⟨sp , d1 ⟩ → ⟨n, d2 ⟩는 만약 d1이 시작점 sp에서 유지한다면 d2도 n을 유지할 것이라는 것을 분석이 결론짓는다는 점을 효과적으로 표현한다.(???????) 우리의 구현에서, 추상-도메인 밸류 di는 taint value들을 참조하는 access path들이다. 두 개의 분석 사이의 handover는 사소하지 않다. 순진하게 협력한다면, 하나는 각각은 context sensitive하지만, 결합했을 때 상충하는 context의 비현실적인 경로를 생성하는 2개의 독립적인 분석 결과를 쉽게 얻을 수 있다. 예를 들면 x.f는 in이 이전에 tainted 되어야만 tainted 되는 것이다. 특히 라인 6은 보고되지 않아야 하는데, taintIT 함수가 "public"이라는 문자열을 전파할 뿐이기 때문이다.

[Figure 3 기반으로 forward, backward 분석을 설명하고, context injection을 하는 이유와 예시를 설명. injection을 하지 않으면 Listing 2의 라인 6이 보고되는 false positive가 발생하기 때문이다.]
Figure 3은 순진한 구현이 어떻게 false positive를 생성하는지, 어떻게 FlowDroid가 하나의 분석에서 다른 분석으로 context를 삽입하는 방법으로 이러한 문제를 다루는지 보여준다. figure은 IFDS 프레임워크의 표기법에 익숙할 것을 가정한다(ㅠㅠㅠ). 블랙 노드는 data-flow facts를 의미, 블랙 레드 엣지는 data-flows를 의미한다. 0는 언제나 true라는 것과 동의어이기 때문에, 0 Node는 언제나 다음과 연결된다. 왼쪽 그림은 전방 탐색이 x.f가 tainted 되었다고 결정하는 것을 보여준다. x.f의 할당을 처리할 때 forward 분석은 backward alias 분석의 인스턴스를 생성한다(오른쪽). 분석을 생성하는 순진한 과정은 0에서 x.f까지의 edge로 초기화하는 것일 것이다. 이러한 구현은 직관적이기는 하지만, x.f의 alias는 무엇이든 관계없이 tain한다는 의미를 가지기 때문에 부정확하다. Listing2에서, 이것은 라인 6의 p2.f까지 부정확하게 보고하는 결과를 낳을 수 있다. 따라서 정확한 방법은 backward 분석에 forward 분석의 context를 삽입하는 방법이다. FlowDroid는 x.f의 "path edge"를 참고한다, 이것은 IFDS 알고리즘이다. 그 이후에 edge 전체를 backward solver에게 삽입한다(알고리즘 1, 라인 16). context 삽입은 forward, backward 모두에서 일어난다. 라인 9에서 out에 대한 backward 분석이 forward 분석을 생성했을 때, 원래의 context인 in을 forward 분석에 삽입했다(알고리즘 2, 라인 17). 의미적으로 두 분석이 taintIT에 대해 발견한 모든 taint들은 in이 초기에 tainted되었는지에 따라 조건적이다.
[backward 분석의 리턴으로 인한 path의 false positive를 막기 위해서, backward가 caller에게 직접 리턴하지 않도록 함. 대신에 backward가 발견한 alias에 대해 forward 분석을 각각 생성하고, 생성된 forward가 caller에게 매핑하는 방법을 사용한다.]
두번째 문제는 비현실적인 path로 인해 발생하는 false positive를 피해야 한다는 것이다. FlowDroid는 backward 분석이 forward 분석에 의해 분석되지 않은 context로 리턴하는 것을 막아야 한다. 이러한 제한을 구현하기 위해서, backward 분석은 caller로 전혀 리턴하지 않는다. 대신에, alias를 발견할 때마다 해당 alias에 대해서 forward 분석을 생성한다, line 9의 out.f 처럼. 이후에는 caller의 context로 관련된 taints들을 다시 매핑하는 것은 forward 분석의 역할이다. Listing 2의 예시에서, forward 분석은 라인 3의 out.f를 p.f로만 매핑할 것이고, p2.f로는 매핑하지 않을 것이다. 핵심은 backward 분석은 callee로는 내려갈 수는 있으나, caller로 리턴하지는 않는다는 것이다, 모든 리턴은 forward 분석에서 처리한다(out이 tainted 되었다고 해서, 리턴하는 것이 아니라 tainted된 out -> p, p를 기준으로 새로운 forward 분석을 생성한다.) backward 분석이 호출을 따라 내려갈 때에, 함수의 첫 번째 라인에 도달하면, 결과적으로는 forward 분석을 생성한다.(알고리즘 2, 라인 13). forward 분석은 그것의 context가 backward 분석에 의해 삽입되었기 때문에 올바른 caller에게 리턴한다는 것을 보장한다.(??) forward 분석이 caller에게 힙 오브젝트와 관련된 taint를 매핑할 때마다, caller 내부에 새로운 alias 검색을 만든다.

Maintaining flow sensitivity

[Listing 3에서 라인 2가 보고되는 경우를 막기 위해 activation statement를 도입. 기본적으로 모든 alias를 inactive한 상태로 두고, backward 분석이 생성하는 forward 분석이 activation statement(출발한 문장?)를 넘어 전파될 때에만 비로소 active로 상태가 변경되고, active한 alias만이 leak이 가능하게 됨.]
Andromeda는 FlowDroid의 on-demand alias 분석에 영감을 준 또다른 taint q분석 도구이다. Andromeda는 그러나 flow-insensitive한 결과를 가져온다. Listing 3의 예시에서 라인 2와 라인 4를 보고할 수 있다, sink가 p2.f가 tainted되기 전에 일어남에도. 사실 FlowDroid의 분석에도 똑같은 문제가 존재한다, backward 분석이 p2를 tainted alias로 발견할지도 모른다.
FlowDroid는 이 문제들을 activation statements라고 부르는 것을 추적함으로써 해결했다. backward alias 분석 인스턴스를 생성할 때에, 각각의 access path를 현재 명령어와 함께 증가된다. tainted alias는 inactive라고 표시된다. 오직 active taints만이 sink에 도달했을 때에 leak을 만들 수 있다. Inactive taints는 아직 tainted 되지 않은 메모리 주소의 alias일 뿐이다. backward 분석이 forward 분석을 다시 생성할 때, forward 분석이 aliased taint를 그것의 activation statement를 넘어 전파할 때에, taint는 비로소 activate 되어 leak을 유발할 능력을 얻게 된다. 예시에서는 activation statement는 라인 3이고, 라인 4의 leak을 유발하면서 라인 2에서의 false alarm을 피하게 된다.
..
FlowDroid는 context- and flow-sensitive한 첫 구현이다. 미래에는 .. 하겠다.(생략)

5. Implementation

FlowDroid는 중요한 요구사항들을 제공해주는 Soot 프레임워크를 확장하였다, three-address code 중간 표현 Jimple, 정확한 call-graph 분석 프레임워크 Spark. Dexpler라고 불리는 플러그인은 Dalvik bytecode를 Jimple로 변환하도록 도와준다. Soot와 Dexpler와 추가적으로, FlowDroid는 IFDS의 구현인 Heros를 이용한다. 우리는 FlowDroid의 아키텍쳐에 대해 설명할 것인데, 구현 디테일과 현재 한계에 대해 설명할 것이다.

Architecture

[사진에 설명된 전반적인 흐름. 1) zip 해제 후 dex, XML 파싱을 통해 lifecycle, callback, source and sink 분석. 2) dummy main 함수 생성. 3) dummy main으로부터 ICFG 생성. 4) taint analysis 진행(Section 4). 5) report 생성]
Android 애플리케이션은 apk로 되어있는데, zip을 해제한 뒤에 lifecycle, callback method, source and sink 호출을 찾는다. 이것은 layout XML, dex 파일 등의 Android-specific 파일들을 파싱하여 이루어진다. 다음, FlowDroid는 dummy main 함수를 lifecycle과 callback 함수들의 리스트로부터 생성한다. 이 main은 call graph를 만들고, inter-procedural control-flow graph(ICFG)를 생성하는 데에 사용된다. 탐지된 source로부터, ICFG를 Section 4에 설명한 방법대로 탐색한다. FlowDroid는 SuSi 프로젝트에서 추론된 source and sink로 설정된다. 구체적인 source와 sink의 리스트는 웹사이트에 있다. 마지막으로 FlowDroid는 모든 발견된 흐름,source to sink를 보고한다. report에는 모든 경로 정보가 포함된다. 이 정보를 얻기 위해, data-flow 추상화 오브젝트를 그들의 조상과 그들의 생성 명령에 연결한다. 이것이 FlowDroid의 리포팅이 모든 관련된 할당 명령어를 완벽히 재구축하도록 만든다.

Defining shortcuts

[라이브러리 처리를 위해 shortcuts 생성.(잘 이해 못함)]
full JRE나 안드로이드 플랫폼을 포함하는 것은 시간도 많이 들고, 추측 대문에 정확성이 낮다. FlowDroid는 외부 라이브러리 모델의 인터페이스와는 타협했다. 도구는 특정한 "shorts rules"을 정의하는 간단한 문자 파일을 지원한다. 미리 정의된 규칙이 collection classes, string buffers, similar commonly used data structure 들을 처리한다. 기술적으로, shortcuts가 call-to-return edge를 이용하여 구현된다. 라이브러리 호출이 연관된 rule이 없다면 완전히 분석된 것이다.

Native calls

[특정 Native Call에 대해서는 explicit taint-propagation rule을 도입하여 처리하고, 나머지 native calls에 대해서는 인자 중에 하나라도 tainted 된 경우 리턴값을 taint로 처리함.]
자바와 안드로이드 플랫폼은 C와 다른 언어로 쓰여진 네이티브 함수 호출을 지원한다. 자바 기반의 분석에서 해당 함수들은 블랙박스, 처리 불가능이다. FlowDroid는 explicit taint-propagation rules을 통해 처리한다. 예를 들어 System.arraycopy 함수에서는 ... explicit rule이 없는 네이티브 함수에 대해서는 하나의 파라미터라도 tainted 되었다면 tainted 되었다는 sensible default를 설정한다. 이것은 올바르거나 정확해보이지는 않지만, 가장 실용적인 추측이다.

Inter-Component Communication

[]
FlowDroid는 intents를 source로 받는 explicit ICC에 대해서 과대평가한다(?). Android는 implicit intent 기반의 통신도 한다. 이런 행동을 동시에 지원하는 것은 future work를 위해 남겨둔다. 특히 우리는 EPICC와 함께 FlowDroid를 통합하는 것에 대해 작업하고 있다.

Limitation

[1) reflective call에서 인자가 string일 때만 지원됨. 2) lifecycle의 callback이나 native 함수가 연구된 것 이외의 새로운 것, 혹은 잘못 처리되었을 때에는 결과가 틀림. 3) 멀티-스레딩을 처리하지 못함.]
FlowDroid가 온전한 분석을 목표로 하지만, 내재된 한계가 있다. FlowDroid는 reflective call에서 그들의 인자가 string 상수일 때에만 처리할 수 있다. 자바 플랫폼에서 TamiFelx와 같은 reflection 분석 도구는 런타임의 reflective 호출을 정적으로 알 수 있도록 한다. 그러한 도구들은 java.lang.instrument를 통해 로드 타임을 알아야 하지만, Android에서는 이것을 지원하지 않는다. 올바르지 않음은 Android lifecycle이 우리가 모르는 callback을 가지고 있을 때, 혹은 우리가 부정확하게 모델링한 native method가 있을 때에도 등장한다.(안드로이드 API 레벨이 새롭게 업데이트 되면 지원이 안되겠네,, 어디까지 지원되나를 살펴보려면 callback이나 native propagation rule을 찾아봐야겠다) 현재 FlowDroid는 멀티-스레딩을 의식하지 못한다. 스레드가 임의의 순서이기는 하지만, 순서대로 동작한다고 가정한다. 멀티스레딩에 대해서 온전히 통합되면서도 올바른 지원을 하는 것은 큰 도전과제이다.

(이후 평가, 비교, DroidBench 등등 생략.)