0. 들어가며

Android static taint analysis는 Android application을 자동화 분석하는 하나의 방법이다. 악성 애플리케이션 분석에 있어 큰 난관 중에 하나는 분석해야할 애플리케이션이 너무나 많다는 것이다. 기존 악성 애플리케이션에서 코드 일부를 바꾸어 새로운 악성 애플리케이션을 자동으로 생성하면, 대응하는 입장에서는 해당 애플리케이션을 처음부터 다시 분석해야 한다. 분석관의 시간은 한정되어 있기 때문에 자동화된 분석은 꼭 필요하다.
FlowDroid라는 도구를 실제로 사용해본 결과, 10분 내외의 시간에 애플리케이션이 사용자의 자료를 유출하고 있는지에 대해 유의미한 결과를 얻을 수 있었다. 애플리케이션 내부의 구조를 모두 파악하고, 가능한 모든 코드 흐름을 분석한다는 정적 분석의 특징을 고려할 때, 합리적인 시간 결과라고 생각했다. 개인 PC가 아닌 분석용 고사양의 PC에서, 내가 탐지하기 원하는 설정을 주면 어렵지 않게 whitelist 애플리케이션 리스트를 생성할 수도 있겠다고 생각해보았다.
이 게시글에서는 android static taint analysis 기법에 대해서 설명하고, 그 중에서 대표라고 할 수 있는 FlowDroid의 동작 원리에 대해서 분석한다. 이어서는 android static taint analysis 연구 분야의 발전 과정에 대해서 설명하고, 앞으로의 응용 분야와 발전 방향에 대해서 이야기하며 마무리짓고자 한다.

1. Android static taint analysis

1.1. Taint Analysis란?

• taint: "오염"이라는 뜻으로 추적의 대상이다. 추적하기를 원하는 데이터에 붙이는 라벨을 taint라고 부른다. tainted 된 데이터로부터 영향을 받은 데이터들은 tainted 된다.
• source: taint 데이터가 생성되는 위치이다. 분석가가 추적하기를 원하는, 관심있는 데이터의 생성 지점을 의미한다. 예를 들어, 사용자의 외부 입력으로부터 미치는 영향을 추적하고 싶다고 하면, 입력을 받는 scanf() 함수가 source가 될 것이다.
• sink: taint 데이터가 도착하는 위치이다. tainted 데이터가 sink에 도착하는지 여부를 파악하는 것이 taint analysis의 목적이다.

Taint analysis는 Data flow Analysis의 일종으로, Program 내부에서 source로부터 생성된 데이터가 sink에 도달하는지 여부를 분석하는 분석이다. 예를 들어 웹 애플리케이션을 분석대상으로 하면, 외부 사용자로부터의 입력 값(source)이 SQL 구문을 실행하는 함수(sink)에 도달하는지를 분석할 수 있다. 외부로부터 유입된 신뢰할 수 없는 데이터가 프로그램 내에서 어떻게 전파되는지를 분석하는 기법이다.

Taint는 프로그램의 실행 흐름에 따라 생성되고, 전파(propagate)되고, 소멸되기도 하는데 위에서 언급했듯이 source로 지정된 함수를 통해 taint는 생성된다. 아래 코드를 보면, X가 20과 같을 경우에는 mov Y, X를 통해 Y에게 전파된다. 한편 X가 20과 같지 않을 때에는 taint가 소멸되기도 한다. taint propagation은 기존에 존재하던 taint의 영향을 받아 새로운 taint가 생성되는 것이다. taint가 전달되는 규칙을 taint propagation rule이라고 한다.

main:
	cmp X, 20 // X is taint
	je if
	jne else
if:
	mov Y, X
else:
	xor X, X 

1.2. Taint analysis on Android application

Android application에 대해서도 taint analysis가 많이 사용된다. 악성 애플리케이션이 많이 등장하고 있고, 심지어는 Googly play protect도 우회 가능하다. 이러한 malware application은 attacker에 의해 생성되기도 하지만, 개발자의 실수에 의해 or 외부 라이브러리의 사용으로 의도적이지 않게 생성되기도 한다.

패러다임의 변화

Taint analysis가 Android application에 적용되면서 패러다임이 조금 바뀐다. taint analysis의 일반적인 목적이 "악성 앱 탐지"이기 때문이다.

• source: 사용자의 개인 정보를 반환하는 함수이다. 사용자의 전화번호, 위치정보, 기기에 대한 정보 등의 데이터가 생성되는 위치이다. 예를 들면, T = telephonymanager.getDeviceId()는 사용자의 IMEI 정보를 반환하는 source 함수이다. source 함수로부터 taint T가 생성된다.
• sink: 데이터가 외부로 유출되는 함수이다. 문자 전송, 외부 인터넷 연결 등에 해당한다. 예를 들면, smsManager.sendTextMessage(T) 함수는 문자를 보내는 함수이다. T가 taint라면, source-sink 연결이 완성되며, 그 결과가 사용자에게 보고된다.

Arzt, S. (2017). Static data flow analysis for android applications.

앞으로 설명할 taint analysis는 android taint analysis를 의미하며, source와 sink도 위에서 설명하는 의미와 동일하게 사용한다.

1.3. Static vs Dynamic taint analysis

정적 분석은 code coverage가 높다는 장점을 가진다. 그러나 프로그램의 런타임 정보에 접근할 수 없기 때문에 정확한 프로그램의 실행을 예측할 수 없어 정확성이 떨어진다는 단점을 가진다. 반면 동적 분석은 실제 실행과 거의 유사하게 동작하기 때문에 정확성이 높다(물론 정상적이게 실행되지 않는다는 점을 감지하여 우회할 여지는 있다). 그러나 프로그램의 실행 속도가 매우 느려질 수 있는데, 동적 분석이 프로그램의 모든 instruction에 control-flow hijacking을 삽입하는 방식으로 구현되기 때문이다.

Why static?

정적 분석은 소스 코드(혹은 컴파일된 코드)를 인풋으로 받아서, 실행시키지 않고 코드를 분석하고, 코드 구조와 문법 순서 의미를 고려하여 변수에 할당된 값들이 어떻게 전달되는지를 파악하는 것이다.

장점으로는 모든 소스코드가 분석된다는 점. 동적 분석에서는 실행할 수 있는 소스코드는 한정되어 있다

대부분의 경우에 정적 분석이 많이 이용되었다. 스토어에 존재하는 수천 개에 앱에 적용하기 위한 확장성을 확보하기 위한 목적이다. 또한 코드 커버리지를 높이기 위해서이다. 그러나 안드로이드 애플리케이션 정적 분석은 쉽지 않은데, 안드로이드만이 가지고 있는 기능들을 고려해야 하기 때문이다. 가장 큰 장벽은, Dalvik bytecode에 대한 분석이 어렵다는 점, Android application에서 main entry point가 없다는 점이다. 이런 것들을 제외하고도, java reflection 등이 어렵다.

Li, L., Bissyandé, T. F., Papadakis, M., Rasthofer, S., Bartel, A., Octeau, D., ... & Traon, L. (2017). Static analysis of android apps: A systematic literature review. Information and Software Technology, 88, 67-95.

2. FlowDroid를 통해 알아보는 static taint analysis

2.1. Considerations

출처: Zhang, J., Wang, Y., Qiu, L., & Rubin, J. (2021). Analyzing android taint analysis tools: FlowDroid, Amandroid, and DroidSafe. IEEE Transactions on Software Engineering.

2.1.1. Android-specific features

Android modeling: 애플리케이션이 Android 실행 환경과 상호작용할 때, 1) 파라미터 중 1개라도 tainted된 경우에는, 리턴 값이 taint 되었다고 추측하거나, 2) Android framework를 정확하게 모델링하는 방법 중 1개를 사용한다.
Component lifecycle: Android application은 4가지 타입의 컴포넌트(Activity, Service, Broadcast Receiver, Content Provider)로 구성되는데, 각각의 컴포넌트는 생성/시작/재개/중지/정지/종료에 대한 lifecycle method를 이용하여 동작한다(참고). 또한 시스템 이벤트, 유저 이벤트에 대해 호출되는 callback 메소드 역시 실행 흐름에 영향을 미친다. 따라서 Static analysis 도구는 컴포넌트의 lifecycle과 이벤트 발생에 따른 callback 메소드를 고려하여야 한다.
Inter-component communication(ICC): 컴포넌트가 다른 컴포넌트와 소통할 때 Intent를 이용하는데, implicit intent는, 요구한 기능을 만족하는 컴포넌트를 Android 시스템이 찾아주도록 하는 것이다. 이러한 implicit intent에서 발생할 수 있는 taint propagation까지 모델링을 할 수 있어야 한다. 비슷한 맥락으로, 서로 다른 앱에 존재하는 컴포넌트 간에 소통하는 것을 IAC(Inter-app communication)이라고 한다.
Native code:

2.1.2. Sensitivities

Li, L., Bissyandé, T. F., Papadakis, M., Rasthofer, S., Bartel, A., Octeau, D., ... & Traon, L. (2017). Static analysis of android apps: A systematic literature review. Information and Software Technology, 88, 67-95.

context-sensitivity: 함수의 호출 위치(call site)을 기준으로 contextual information을 파악하는 것이다. 아래 그림에서 sink() 함수가 호출되는 위치는 foo()와 bar()의 2개가 존재한다. context-sensitivity란, 서로 다른 위치에 있는 서로 다른 flow를 다르게 인식할 수 있는 것이다.
object-sensitivity: 함수를 호출한 객체의 할당 지점을 지준으로 contextual information을 파악하는 것이다. 아래 그림에서 sink() 함수는 서로 다른 객체 a1, a2로부터 호출되는데, a1과 a2의 할당 지점, 객체의 내부 변수 등 heap object를 고려하는 것이다. object-sensitivity란, 서로 다른 객체로부터의 함수 호출을 서로 다르게 인식할 수 있는 것이다.

field-sensitivity: 같은 객체 내에서 서로 다른 필드들을 구별할 수 있는 것이다.
flow-sensitivity: 명령어들의 순서를 고려하는 것이다. 예를 들어 아래 코드에서 y=1 이라고 올바르게 인식해야 한다.

x = 1
y = x
x = 2

• path-sensitivity: 분기문에 따른 path에 대한 정보를 고려하는 것이다. x > 0이라는 분기 조건이 있다면, 참인 부분의 코드에서는 x > 0임이 전제되어야 하고, 거짓인 부분의 코드에서는 x <= 0임이 전제되어야 한다.

2.1.3. Implicit flows

tainted data가 실행 흐름에 간접적으로 영향을 주어, 관찰되는 값을 바뀌게 하는 것이다. 예를 들어 아래 코드에서 taint는 직접적으로 전달되지 않으나, 출력되는 값을 다르게 하고 있다.

if(taint):
	print(True)
else:
	print(False)

2.1.4. Java-specific features

Reflection: 자바에서 클래스, 인터페이스, 메소드들을 찾을 수 있고, 객체를 생성하거나 변수를 변경할 수 있고 메소드를 호출할 수도 있다. Hidden method를 호출하거나, private 변수를 변경할 수도 있다. 악성 앱들에서 민감한 정보를 숨길 때에 이용될 수도 있는 기능이다.

Class clazz = Class.forName("test.Child");
Child child = new Child();

// Constructor 찾기
Constructor constructors[] = clazz.getDeclaredConstructors();
for (Constructor cons : constructors) {
    System.out.println(cons); // private test.Child(java.lang.String), public test.Child()
}

// Method 찾기
Method methods[] = clazz.getDeclaredMethods();
for (Method method : methods) {
    System.out.println(method); // public int test.Child.method4(int), private int test.Child.method5(int)
}

// Field 찾기
Field field = clazz.getDeclaredField("cstr1");
System.out.println(field); // public java.lang.String test.Child.cstr1

// Method 호출
Method method = clazz.getDeclaredMethod("method5", int.class);
method.setAccessible(true); // private 메소드 접근 가능하도록 변경
int returnValue = (int) method.invoke(child, 10);

// Field 변경
Field fld = clazz.getField("cstr1");
fld.set(child, "cstr1");

// Static 메소드 호출
Method method = clazz.getDeclaredMethod("exampleStaticMethod", int.class);
method.invoke(null, 10);

Exceptions: 예외도 동적으로 호출되고, 예외의 타입도 상황에 따라 달라지기 때문에 예외를 정확하게 처리하는 것은 어렵다.

2.2. Flowdroid 소개

Flowdroid는 2014년에 처음 등장한 Android application static analysis 도구이다. Google Scholar 기준 현재 2135회 인용되었으며, Github도 약 700개의 star를 받고 있다. 현재 존재하는 static analysis 도구들 중에서 뛰어난 성능을 보이고 있으며, 현재까지 계속 업데이트되고 있는 유일한 도구이다. 따라서 성능면에서나, 유지보수면에서나 Flowdroid를 사용할 수 밖에 없는 상황이다. 뒤에서 다시 살펴볼 supporting tools 역시 같은 이유로 Flowdroid와 같은 환경 설정에서 사용할 수 있도록 제작되었다.

Arzt, S., Rasthofer, S., Fritz, C., Bodden, E., Bartel, A., Klein, J., ... & McDaniel, P. (2014). Flowdroid: Precise context, flow, field, object-sensitive and lifecycle-aware taint analysis for android apps. Acm Sigplan Notices, 49(6), 259-269.

FlowDroid는 flow-, context-, field-, object-sensitive한 static taint analysis 도구이다. Android lifecycle과 UI object의 callback을 처리할 수 있어 taint propagation을 정확하게 계산할 수 있다. Reflective call에 대해서는 constant string만 처리할 수 있다. 이전 버전에서는 implicit flow를 처리하지 않았으나, 최근에는 처리가 가능하다.

2.3. Flowdroid: Architecture

APK to Callgraph

• Soot: Java bytecode to Jimple, Construct callgraph
• Jimple: Java intermediate representation.

IFDS framework

IFDS(interprocedural, finite, distributive, subset problems)
Callgraph를 기반으로 dataflow-analysis를 poly-time 내에 풀어낼 수 있도록 하는 알고리즘

Flowdroid Architecture

Soot 기반으로 Callgraph를 생성하고, Callgraph 기반으로 IFDS Solver가 그래프를 탐색한다. 그래프를 탐색하는 과정에서 taint를 정의하고, taint가 생성되고 전달되고 삭제되고 하는 모든 과정을 다루는 곳이 FlowDroid core이다. FlowDroid core에서 필요한 여러 기능들을 제공하는 것들이 나머지이다.

2.4. Flowdroid: Lifecycle Modeling

Component lifecycle

Android application들은 컴포넌트로 구성되고, 컴포넌트는 Activity, Service, Content Provider, Broadcast Receiver 중에 하나로 선택된다. 이러한 컴포넌트들은 아래와 같이 AndroidManifest.xml 파일에 등록되어 있다.

<activity android:name="ShareActivity">
    <intent-filter>
        <action android:name="android.intent.action.SEND"/>
        <category android:name="android.intent.category.DEFAULT"/>
        <data android:mimeType="text/plain"/>
    </intent-filter>
</activity>

2.1.1.에서 언급한 것과 같이 각각의 컴포넌트들은 lifecycle을 갖는데, lifecycle들의 가능한 조합들을 모두 고려하는 작업이 반드시 필요하다. 예를 들어 유저가 한 화면에서 다른 화면으로 넘어갈 경우에 onResume()에서 onPause(), onStop()으로 흐름이 넘어가고, 다른 화면에서 다시 돌아올 경우에는 onRestart() 혹은 onCreate()로 흐름이 이어진다. 이러한 lifecycle 메소드는 각각의 데이터 흐름을 가지고 있고, 정적 분석하는 입장에서 어떻게 실행될지 모르기 때문에, 정확한 분석을 위해서는 가능한 모든 lifecycle 조합을 고려해야 한다.

Component의 실행 순서

컴포넌트의 실행 순서는 예측할 수가 없는데, User input에 따라 실행되는 컴포넌트가 달라지기 때문이다. 예를 들면 유저가 선택하는 버튼에 따라 어떤 컴포넌트가 전면에 등장할지가 달리지기 때문이다. 따라서 Flowdroid는 컴포넌트들의 실행 순서를 '임의의 순서'로 가정한다.
또한 시스템&유저 이벤트(위치 변화, UI 버튼 클릭 등)에 따라 callback이 실행되기도 하는데, 이 경우에도 callback의 실행 순서는 예측할 수 없기 때문에 Flowdroid는 모든 callback이 임의의 순서로 실행된다고 가정한다. 예를 들어 악성코드 개발자가 onPause() 혹은 onDestroy() 함수 내부에 sink()에 해당하는 함수들을 배치할 수도 있다. 따라서 callback과 같이 실행 흐름을 예측할 수 없는 경우에는 아래 그림과 같이 가능한 모든 순서로 실행된다고 가정한다.

지금까지의 과정을 종합해서 dummy main 함수를 생성한다. component들의 lifecycle을 고려하고, 거기에다가 callback 함수의 가능한 모든 조합을 합친 후에, 앱에 존재하는 모든 component들을 합쳐서 앱 별로 1개의 dummy main을 만든다.

2.5. Flowdroid: Taint propagation

Taint Propagation rules

Normal flow: x.f = y.g와 같이 call이나 return이 없는 흐름.

Call flow: 함수를 호출하는 흐름. caller to callee.

Return flow: 원래의 함수로 반환하는 흐름. callee to caller.

Call-to-return flow: callee로 들어가지 않고 바로 반환되는 흐름. Native 함수 등을 이렇게 처리함

위에서 언급한 것은 Normal taint propagation이고, Flowdroid에서는 Backward taint propagation rules를 별도로 가지는데, 이 부분은 생략한다.

Modeling the Android framework

Android framework가 제공하는 수많은 라이브러리들을 각각의 애플리케이션을 분석할 때마다 새롭게 분석하는 것은 번거롭고, 시간이 오래 걸린다. 또한 Android SDK는 업데이트가 잦은 편인데, 새로운 API 버전이 출시될 때마다 이를 새롭게 분석하는 일 역시 번거롭다.
따라서 Stubdroid라는 것을 만들어, Flowdroid가 Android framework들을 미리 계산하여 저장해 놓은 데이터를 빠르게 가져다 쓸 수 있도록 하였다. Stubdroid는 Taint analysis에 필요한 정보로 구성된다. 예를 들자면, 세 번째 파라미터가 taint일 때에만 return value가 tainted 된다든지 이런 정보를 xml 형태로 가지고 있게 된다.

Handling Native Functions

자바(안드로이드)는 C나 C++로 생성된 라이브러리를 호출하여 사용할 수 있도록 하는데, 이를 Native 라이브러리라고 한다. 성능 향상을 할 수 있어 Native 라이브러리를 주로 사용하며, 최근 더 비중이 커지고 있다. Android framework에서도 Native 라이브러리를 사용하는 경우들이 있는데, 이 경우에는 위에 언급한 Stubdroid에서 처리하고 있다. 2017년 논문 기준 70%의 앱에서 적어도 1개의 Native 라이브러리를 사용하고 있다고 하니, 중요도가 점점 높아지고 있다.

문제는 Flowdroid 입장에서 Native 라이브러리는 완전 blackbox와 같다는 점이다. 이유는 Flowdroid는 오로지 Java 언어만을 처리할 수 있기 때문이다. 따라서 Native 함수에 대한 기본 전략은 over-approximation이다. 쉽게 설명하자면, 함수의 파라미터 중 1개라도 tainted된 경우에는 나머지 파라미터 및 return value를 모두 tainted라고 간주하는 것이다.

다만, Android framework에 해당하는 Native 라이브러리, 주로 사용되는 Native 라이브러리는 Stubdroid에 통합되어 정확하고 빠르게 제공된다. 또한 저자의 말을 빌리면 sensitive 한 데이터의 흐름이 Native 라이브러리로 이어지는 경우는 잘 없다고 한다(솔직히 공감하기는 힘들다)

3. 논문 230편을 통해 정리한 연구 동향

3.1. ~2015년: 연구 분야의 탄생

Li, L., Bissyandé, T. F., Papadakis, M., Rasthofer, S., Bartel, A., Octeau, D., ... & Traon, L. (2017). Static analysis of android apps: A systematic literature review. Information and Software Technology, 88, 67-95.

연구의 목적은 개인정보 유출 탐지, 취약점 발견이다.

2011 ~ 2015년에 발표된 android static analysis 통계, taint analysis가 가장 많은 비율을 차지하는 것을 볼 수 있다.

연구 분야가 급격하게 성장하는 것을 볼 수 있다.

그 중에서도 대표적인 논문은 Droidsafe(NDSS 2015, 473회 인용), Flowdroid(Acm Sigplan Notices 2014, 2135회 인용), Amandroid(ACM CCS 2014, 469회 인용), Androidleaks(
International Conference on Trust and Trustworthy Computing 2012, 794회 인용), Iccta(IEEE ICSE, 636회 인용)

3.2. ~2018년: 연구 발전 climax

1
대표적인 도구들이 자리를 잡기 시작하였음
Flowdroid는 Iccta와 통합, Stubdroid를 이용하여 Android 모델링 강화, implicit flow 지원 등등
Amandroid는 2014년 이후

2
대표적인 도구들의 성능을 비교하려는 논문들이 등장함
Analyzing the analyzers: Flowdroid/iccta, amandroid, and droidsafe
Do android taint analysis tools keep their promises?
Discovering flaws in security-focused static analysis tools for android using systematic mutation
A qualitative analysis of Android taint-analysis results(2019)

3
Static analysis의 challenge들을 해결하려는 논문들이 등장함
Native: Jn-saf
Reflection: droidra
ICC: EPICC, Iccta

4
대표적인 도구들을 활용하는 논문들이 등장하기 시작함

애플리케이션 취약점 스캐닝. Flowdroid, Androbugs 이용
Poster: On Vulnerability Evolution in Android Apps

애플리케이션 중복(redundancy) 제거
RedDroid: Android application redundancy customization based on static analysis

3.3. 2019년~: 다양한 분야로의 발전

Energy leakage(Wake lock)
Detecting energy bugs in android apps using static analysis(2017)
Sentinel: generating GUI tests for Android sensor leaks(2018)
Wake Lock Leak Detection in Android Apps Using Multi-Layer Perceptron

효율성을 강조한 taint analysis 도구
An efficient approach for taint analysis of android applications
FastDroid

응용
Taint anlaysis를 이용하여 안드로이드 사전 설치된 앱에서 권한 상승 취약점을 850개 발견.
FIRMSCOPE: Automatic uncovering of privilege-escalation vulnerabilities in pre-installed apps in android firmware

직접적인 inter-app code invocation을 탐지
Borrowing your enemy's arrows: the case of code reuse in android via direct inter-app code invocation

디자인 패턴의 탐지
A model based approach for android design patterns detection

앱의 아이콘과 실제 행동에서의 불일치를 탐지
DeepIntent: Deep icon-behavior learning for detecting intention-behavior discrepancy in mobile apps

Machine Learning에 도움을 주는
feature reduction을 실험하기 위해 안드로이드 APK의 제어흐름 분석을 수행함
안드로이드 악성코드 분류를 위한 Flow Analysis기반의 API 그룹화 및 빈도 분석 기법

Hybrid 접근들이 늘어남:
정적 분석에 dynamic heap snapshot을 조금이라도 추가했을 때 정확성이 높아짐을 평가
Heaps'n Leaks: How heap snapshots improve android taint analysis

앱을 분석하기 위해 정적 분석과 동적 분석을 함께 사용하였음
A longitudinal study of application structure and behaviors in android

4. Future works

Static Analysis 기술만으로는 한계에 부딪혔다고 본다.

• Native 라이브러리의 비중 증가
  • 하이브리드 앱, 프로그레시브 웹 앱(PWA)의 등장
  • Flutter, React Native 등 크로스 플랫폼 프레임워크의 등장
• 정확도 & 시간에서의 이슈
  • 분석 정확도
    전체 82개의 Exp. Flows 중에서 19개의 TP(True Positive)만을 발견한 것을 볼 수 있음.
    
  • 앱 1개 분석 시간 (최소 1분, 최대 20.2시간, 평균 2.8시간, 중앙값 11분)
    

Static analysis를 단독으로 사용하기 보다는 활용하는 추세이다. 연구가 계속 진행되고 있는 분야로는,

• 머신러닝에 활용하기 위한 feature 들을 파악하기 위해서
• Wake lock Detection, Energy Leak
• Sofeware Debloating, Application redundancy

Apply to Digital Forensics

• taint analysis의 개념을 응용하여 디지털 포렌식에 활용할 수 있다. source를 추적하고 싶은 개인정보로, sink를 데이터의 저장 위치, 클라우드 등 원격 저장 URL로 설정한다. application을 분석할 필요 없이 어떤 데이터가 어디에 저장되는지를 쉽게 확인할 수 있다.
  Automated forensic analysis of mobile applications on Android devices