Symbolic execution based control flow graph extraction method for Android native codes

Hui-ying YAN; Zhen-ji ZHOU; Li-fa WU; Zheng HONG; He SUN

doi:10.11959/j.issn.2096-109x.2017.00178

您当前的位置：

首页 >

文章列表页 >

Symbolic execution based control flow graph extraction method for Android native codes

Papers | 更新时间：2024-06-03

- Symbolic execution based control flow graph extraction method for Android native codes
- Chinese Journal of Network and Information Security Vol. 3, Issue 7, Pages: 33-46(2017)
- 作者机构：
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.2096-109x.2017.00178
  CLC： TP309
- Online First：2017-07，
  
  Published：15 July 2017
- 稿件说明：
移动端阅览
Hui-ying YAN, Zhen-ji ZHOU, Li-fa WU, et al. Symbolic execution based control flow graph extraction method for Android native codes[J]. Chinese Journal of Network and Information Security, 2017, 3(7): 33-46.
DOI：

Hui-ying YAN, Zhen-ji ZHOU, Li-fa WU, et al. Symbolic execution based control flow graph extraction method for Android native codes[J]. Chinese Journal of Network and Information Security, 2017, 3(7): 33-46. DOI： 10.11959/j.issn.2096-109x.2017.00178.

摘要

提出了一种基于符号执行的控制流图提取方法，该方法为原生库中的函数提供了符号执行环境，对JNI 函数调用进行模拟，用约束求解器对符号进行求解。实现了控制流图提取原型系统 CFGNative。实验结果表明，CFGNative可准确识别样例中所有的JNI函数调用和原生方法，并能够在可接受的时间内达到较高的代码覆盖率。

Abstract

A symbolic execution based method was proposed to automatically extract control flow graphs from native libraries of Android applications.The proposed method can provide execution environments for functions in native libraries

simulate JNI function call processes and solve symbols using constraint solver.A control flow graph extraction prototype system named CFGNative was implemented.The experiment results show that CFGNative can accurately distinguish all the JNI function calls and native methods of the representative example

and reach high code coverage within acceptable time.

关键词

Keywords

references

Statista . number of apps available in leading app stores as of march 2017 [EB/OL ] . https://www.statista.com/statistics/276623/number-ofapps-available-in-leading-app-stores/ https://www.statista.com/statistics/276623/number-ofapps-available-in-leading-app-stores/ .

SCHWARZ B , DEBRAY S , ANDREWS G . Disassembly of executable code revisited [C ] // The Working Conference on Reverse Engineering . 2002 : 45 - 54 .

KRUEGEL C , ROBERTSON W , VALEUR F , et al . Static disassembly of obfuscated binaries [C ] // Usenix Security Symposium . 2004 : 255 - 270 .

REPS T , HORWITZ S , SAGIV M . Precise interprocedural dataflow analysis via graph reachability [C ] // The 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages . 1995 : 49 - 61 .

HORWITZ S , REPS T , BINKLEY D . Interprocedural slicing using dependence graphs [J ] . ACM Sigplan Notices , 2004 , 23 ( 7 ): 35 - 46 .

BRUSCHI D , MARTIGNONI L , MONGA M . Detecting self-mutating malware using control-flow graph matching [C ] // The International Conference on Detection of Intrusions and Malware and Vulnerability Assessment , 2006 : 129 - 143 .

CESARE S , XIANG Y . Malware variant detection using similarity search over sets of control flow graphs [C ] // The International Conference on Trust,Security and Privacy in Computing and Communications . 2011 : 181 - 189 .

CIFUENTES C , VAN EMMERIK M . Recovery of jump table case statements from binary code [C ] // The International Workshop on Program Comprehension . 1999 : 192 - 199 .

MENG X , MILLER B P . Binary code is not easy [C ] // The 25th International Symposium on Software Testing and Analysis . 2016 : 24 - 35 .

SUTTER B D , BUS B D , BOSSCHERE K D , et al . On the Static Analysis of Indirect Control Transfers in Binaries [C ] // The International Conference on Parallel ＆Distributed Processing Techniques ＆Applications . 2000 : 1013 - 1019 .

KINDER J , ZULEGER F , VEITH H . An abstract interpretation-based framework for control flow reconstruction from binaries [C ] // The International Workshop on Verification,Model Checking,and Abstract Interpretation . 2009 : 214 - 228 .

TROGER J , CIFUENTES C . Analysis of virtual method invocation for binary translation [C ] // The Working Conference on Reverse Engineering . 2002 : 65 - 74 .

JOHNSON R , STAVROU A . Forced-path execution for android applications on x86 platforms [C ] // The International Conference on Software Security and Reliability Companion . 2013 : 188 - 197 .

XU L , SUN F , SU Z . Constructing Precise Control Flow Graphs from Binaries [J ] . University of California . 2012 .

ZHAO J , . Analyzing control flow in Java bytecode [C ] // The 16th Conference of Japan Society for Software Science and Technology . 1999 : 313 - 316 .

胡刚 , 张平 , 李清宝 , 等 . 基于静态模拟的二进制控制流恢复算法 [J ] . 计算机工程 , 2011 , 37 ( 5 ): 276 - 278 .

HU G , ZHANG P , LI Q B , et al . Control flow restoring algorithm for binary program based on static simulation [J ] . Computer Enginerring , 2011 , 37 ( 5 ): 276 - 278 .

张雁 , 林英 . 程序控制流图自动生成的算法 [J ] . 计算机与数字工程 , 2010 , 38 ( 2 ): 28 - 30 .

ZHANG Y , LIN Y . Automatic generation algorithm of the control flow graph [J ] . Computer ＆Digital Engineering , 2010 , 38 ( 2 ): 28 - 30 .

ARZT S , RASTHOFER S , FRITZ C , et al . FlowDroid:precise context,flow,field,object-sensitive and lifecycle-aware taint analysis for android Apps [J ] . ACM Sigplan Notices , 2014 , 49 ( 6 ): 259 - 269 .

LI L , BARTEL A , BISSYANDE T F , et al . Iccta:Detecting inter-component privacy leaks in android Apps [C ] // The International Conference on Software Engineering . 2015 : 280 - 291 .

WEI F , ROY S , OU X . Amandroid:a precise and general inter-component data flow analysis framework for security vetting of android apps [C ] // The 2014 ACM SIGSAC Conference on Computer and Communications Security . 2014 : 1329 - 1341 .

辛纳(美) . Android C++高级编程——使用NDK [M ] . 北京 : 清华大学出版社 , 2013 .

CINAR O . Pro Android C++ wih the NDK [M ] . Beijing : Tsinghua University PressPress , 2013 .

Angr . Intermediate Representation [EB/OL ] . https://docs.angr.io/ docs/ir.html https://docs.angr.io/ docs/ir.html .

NETHERCOTE N , SEWARD J . Valgrind:a framework for heavyweight dynamic binary instrumentation [J ] . Acm Sigplan Notices , 2007 , 42 ( 6 ): 89 - 100 .

YAN S , WANG R , HAUSER C , et al . Firmalice-automatic detection of authentication bypass vulnerabilities in binary firmware [C ] // The Network and Distributed System Security Symposium , 2015 .

SHOSHITAISHVILI Y , WANG R , SALLS C , et al . SOK:(State of) the art of war:offensive techniques in binary analysis [C ] // Security and Privacy . 2016 : 138 - 157 .

Views

8456

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Metrics for code obfuscation based on symbolic execution and N-scope complexity

Security protocol code analysis method combining model learning and symbolic execution

Code vulnerability detection method based on graph neural network

Research on construction of conditional exception code used in branch obfuscation

Software patch comparison technology through semantic analysis on function

Related Author

Yuqiang XIAO

Yunfei GUO

Yawen WANG

Xieli ZHANG

Yuefei ZHU

Chunxiang GU

Xi CHEN

Hao CHEN

Related Institution

State Key Laboratory of Mathematical Engineering and Advanced Computing

Henan Key Laboratory of Network Cryptography Technology

State Key Laboratory of Mathematical Engineering ＆Advanced Computing

Henan University of Engineering

⁰