N-Gram 是常用於文件檢索的特徵擷取方式，透過 N-Gram 的不同組合可以取得多 樣化的特徵。針對程式的特徵擷取，通常的做法是使用沙盒(Sandbox)模擬執行，建構數 據蒐集環境進行動態分析，擷取系統函數呼叫、執行時期網路與系統資源使用等，且需 要複雜的環境設定。本論文提出使用靜態分析方法，透過 N-Gram 擷取出操作碼(Opcode)， 並且加上其出現的頻率來評估 Android 作業系統上的應用程式，比起動態分析不需要執 行程式，在原始檔案即可進行分析。透過計算特徵出現的頻率，並使用資訊增益 (Information Gain)與資訊量增益比例(Information Gain Ratio)兩種特徵選取方法，搭配支 援向量機(SVM)與徑向基底函數網路(Radial basis function network, RBF Net)兩種分類器， 來評估機器學習對於 Android 惡意程式分類之成效。實驗結果顯示，在使用資訊增益搭 配 RBF Net，在 3-Gram 即可達到 G-Mean 0.96 及 MAE 0.0547。因此可以驗證所提出方 法，能有效分類惡意程式。

N-Gram is a feature extraction method commonly used in information retrieval, while it can get lots of different combinations of features. For the feature extraction of the program, the usual practice is to use sandbox for execution simulation and construct a data collection environment for dynamic analysis. It usually captures system function calls, to monitor run- time network and system resource usage, etc..., which needs complex environment settings. This paper proposes to use the static analysis method to extract the opcodes through N-Gram and get the frequency of its occurrence for the application programs in the Android operating system. Compared to the dynamic analysis, the application program doesn’t need to be executed. And can be analyzed in its original form. After calculating the frequency of the opcode feature, we use two feature selection methods information gain and the information gain ratio, with two classifiers support vector machine and radial basis function network to evaluate the effectiveness for Android malware classification. The experimental results show that G-Mean 0.96 and MAE 0.0547 can be achieved in 3-Gram when using the information gain with RBF Net. Therefore, the effectiveness of the proposed method in classifying Android malware can be effectively classified.

摘 要...........................................................................................................................................i
ABSTRACT ............................................................................................................................... ii
誌 謝.........................................................................................................................................iv
目 錄..........................................................................................................................................v
圖目錄 ...................................................................................................................................... vii
表目錄 ..................................................................................................................................... viii
第一章 緒論..............................................................................................................................1
1.1 研究背景與動機 ............................................................................................................. 1
1.2 研究目的 ......................................................................................................................... 1
1.3 研究貢獻 ......................................................................................................................... 2
1.4 章節概要 ......................................................................................................................... 2
第二章 相關研究......................................................................................................................4
2.1 靜態分析 (Static Analysis) ............................................................................................ 4
2.1.1 惡意程式 N-Gram 特徵擷取 ................................................................................... 4
2.1.2 執行檔封裝資訊 ...................................................................................................... 5
2.1.3 操作碼 (Opcode).....................................................................................................5
2.2 動態分析 (Dynamic Analysis)....................................................................................... 6
2.3 資訊增益(InformationGain)..........................................................................................6
2.4 支援向量機(Support Vector Machine)........................................................................... 6
第三章 實驗設計......................................................................................................................7
3.1 Benign Crawler & Checker .............................................................................................. 8
3.2 Feature Extraction ............................................................................................................ 9
3.2.1 APK File ........................................................................................................................ 9
3.2.2 APK Tool..................................................................................................................... 10
3.2.3 Dalvik 操作碼 ............................................................................................................. 11
3.2.4 操作碼N-Gram特徵擷取.........................................................................................11
3.3 Malware Classification................................................................................................... 13
3.3.1 Information Gain Ratio................................................................................................ 14
3.3.2 RBF Net ....................................................................................................................... 15
第四章 實驗方法....................................................................................................................16
4.1 實驗環境 ....................................................................................................................... 16
4.2 實驗平台 ....................................................................................................................... 16
4.3 實驗資料集 ................................................................................................................... 16
4.4 驗證方法 ....................................................................................................................... 17
4.5 實驗一:分類器方法比較...........................................................................................19
4.6 實驗二:特徵選取方法比較 ........................................................................................ 24
4.6 實驗三:比較特徵值...................................................................................................27
第五章 結論............................................................................................................................28
5.1 研究結論....................................................................................................................... 28
5.2 後續研究建議............................................................................................................... 28
參考文獻 .................................................................................................................................. 29

[1] eMarketer(2017, Dec), Worldwide Internet and Mobile Users: eMarketer's Updated Estimates and Forecast for 2017–2021, https://www.emarketer.com/Report/Worldwide-Internet-Mobile Users-eMarketers-Updated-Estimates-Forecast-20172021/2002147 (Viewed on 2018/05/18)
[2] Statista(2018), App stores: number of apps in leading app stores 2017 | Statistic, https://www.statista.com/statistics/276623/number-of-apps-available-in-leading-app-stores/ (Viewed on 2018/05/18)
[3] IDC, Smartphone OS, https://www.idc.com/promo/smartphone-market-share/os (Viewed on 2018/05)
[4] Securelist(2018, Mar), Mobile malware evolution 2017, https://securelist.com/mobile-malware-review-2017/84139/ (Viewed on 2018/05)
[5] Kenna security , Kenna Security’s Remediation Gap, https://www.kennasecurity.com/wp-content/uploads/KennaNonTargetedAttacksReport.pdf (Viewed on 2017/08/18)
[6] Apkpure, https://apkpure.com/
[7] Virustotal, https://www.virustotal.com/
[8] APK Tool, https://ibotpeaches.github.io/Apktool/
[9] Shafiq, M. Z., Khayam, S. A., & Farooq, M. (2008, July). Embedded malware detection using markov n-grams. In International Conference on Detection of Intrusions and Malware, and Vulnerability Assessment (pp. 88-107). Springer, Berlin, Heidelberg.
[10] Yerima, S., Sezer, S., & Muttik, I. (2015) High accuracy Android malware detection using ensemble learning. IET Information Security, 9(6), 313–320.
[11] Cortes, C., & Vapnik, V. (1995). Support-vector networks. Machine learning, 20(3), 273- 297.
[12] Baskaran, B., & Ralescu, A. (2016). “A Study of Android Malware Detection Techniques and Machine Learning.” In Modern Artificial Intelligence and Cognitive Science Conference. eCommence.
[13] Kubat, M. and Matwin, S., “Addressing the curse of imbalanced training sets: onesided selection,” in International Conference on Machine Learning. Morgan Kaufmann,
1997, pp. 179–186.
[14] McLaughlin, N., Doupé A., Del Rincon, J. M., Kang, B. J., et al., “Deep android malware detection,” in The Seventh ACM on Conference on Data and Application Security and Privacy (CODASPY), pp. 301–308, Scottsdale, Arizona, USA, March 2017.
[15] Kang, B., Yerima, S. Y., Sezer, S., & McLaughlin, K. (2016). N-gram Opcode Analysis for Android Malware Detection. arXiv preprint arXiv:1612.01445.
[16] Jerome, Q., Allix, K., State, R., & Engel, T. (2014, June). Using opcode-sequences to detect malicious Android applications. In 2014 IEEE International Conference on Communications (ICC), (pp. 914-919). IEEE.
[17] Schultz, M. G., Eskin, E., Zadok, F., & Stolfo, S. J. (2001). Data mining methods for detection of new malicious executables. In Proceedings of 2001 IEEE Symposium on ecurity and Privacy, (2001 S&P 2001S). (pp. 38-49). IEEE.
[18] Chan, P. P., & Song, W. K. (2014, July). Static detection of Android malware by using permissions and API calls. In 2014 International Conference on Machine Learning and Cybernetics (ICMLC), (Vol. 1, pp. 82-87). IEEE.
[19] Su, M. Y., Fung, K. T., Huang, Y. H., Kang, M. Z., & Chung, Y. H. (2016, July). Detection of Android malware: Combined with static analysis and dynamic analysis. In 2016 International Conference on High Performance Computing & Simulation (HPCS),(pp. 1013-1018). IEEE.
[20] Wei, T. E., Mao, C. H., Jeng, A. B., Lee, H. M., Wang, H. T., & Wu, D. J. (2012, June). Android malware detection via a latent network behavior analysis. In 2012 IEEE 11th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom), (pp. 1251-1258). IEEE.
[21] Nix, R., & Zhang, J. (2017, May). Classification of Android apps and malware using deep neural networks. In 2017 International Joint Conference on Neural Networks (IJCNN), (pp. 1871-1878). IEEE.
[22] Yeh, C. W., Yeh, W. T., Hung, S. H., & Lin, C. T. (2016, October). Flattened data in convolutional neural networks: using malware detection as case study. In Proceedings of the International Conference on Research in Adaptive and Convergent Systems (pp. 130- 135). ACM.
[23] Canfora, G., De Lorenzo, A., Medvet, E., Mercaldo, F., & Visaggio, C. A. (2015, August). Effectiveness of opcode ngrams for detection of multi family android malware. In 2015 10th International Conference on Availability, Reliability and Security (ARES), (pp. 333-340). IEEE.
[24] Aafer, Y., Du, W., & Yin, H. (2013, September). Droidapiminer: Mining api-level features for robust malware detection in android. In International conference on security and privacy in communication systems (pp. 86-103). Springer, Cham.
[25] Santos, I., Penya, Y. K., Devesa, J., & Bringas, P. G. (2009). N-grams-based File Signatures for Malware Detection. ICEIS (2), 9, 317-320.
[26] Upchurch, J., & Zhou, X. (2013, October). First byte: Force-based clustering of filtered block N-grams to detect code reuse in malicious software. In 2013 8th International Conference on Malicious and Unwanted Software:" The Americas"(MALWARE), (pp. 68-76). IEEE.
[27] Bartel, A., Klein, J., Le Traon, Y., & Monperrus, M. (2012, June). Dexpler: converting android dalvik bytecode to jimple for static analysis with soot. In Proceedings of the ACM SIGPLAN International Workshop on State of the Art in Java Program analysis (pp. 27-38). ACM.