本論文主要是在探討依序選擇四個字串之下，是否存在一策略使得第二或第四字串有較大的機會比第一或第三字串先出現，也就是所謂的後選優勢是否存在。 利用電腦計算，我們發現字串長度為4,5,6時後選優勢確實存在，而當字串長度大於等於或等於7時，我們則證明了若第一字串為(0,0,...,0),(0,0,...,0,1),(1,1,...,1)或(1,1,...,1,0)時，後選者優勢亦存在。 / In the thesis, we consider about the first occurrence of four strings decided sequentially with teams. Team 1 consists string 1 and string 3; team 2 consists string 2 and string 4. It is interested in whether or not team 2 whose strings are decided after first string and third string are given separately gets an advantage in appearing with larger probability.Namely, given any string 1, we want to find a string 2 such that any string 3 corresponds to at least one string (string 4) making a larger probability for team 2 in appearing earlier than team 1. Based on the result from computer calculation, team 2 advantage over team 1 when the string length is 4, 5, and 6. This thesis also shows that team 2 gets an advantage for cases where string 1 is (0,0,...,0), (0,0,...,0,1), (1,1,...,1), (1,1,...,1,0) ,when the string length is larger than 6.

本研究所要討論的是如何以局部區域的數值高程模型資料辨識出所在整體地形的相對應位置。數值高程模型是以網格式的方式描述地表上連續性的起伏變化，以二維陣列儲存地表高度的資料，包含三度空間的特性。 我們從區域地形萃取出線性特徵與點特徵，分別為水系河段與地形上較明顯的凸點與凹點，以水系作為識別每一區域地形的“指紋”，對於地形變化小或河段特徵不明顯之區域尋找其特徵點，配合相關地形參數與整體地形進行比對，並對不同之特徵採用不同比對演算法。我們以物件化的方式表達水系河段與特徵點，將許多圖層的資訊整合於物件中，除了方便資料的管理，也加快了比對的效率。實驗結果顯示，應用此兩種特徵值作為辨識地形依據，可有效辨識出正確位置，也節省許多不必要的比對時間。 / The main objective of this thesis is to identify a terrain using partial Digital Elevation Model (DEM) information. DEM is one of the most commonly used data representation models used in Geographical Information Systems. It is a digital model with an array of uniformly spaced elevation data in raster format. One can use DEM to analyze terrain measures including slope, aspect, and other features. In the thesis, we use hydrology analysis to extract the stream networks and use terrain parameter analysis to compute terrain features from the DEM of a small region. This information can be used as the “fingerprints” of the terrain and then compare them with the “fingerprints” in the whole data base in order to identify or to locate the correct location of the region. The KMP string matching algorithm is used to speed up the matching process. Measurements extracted from DEM through hydrology analysis may not provide significant terrain information for the identification purpose. In this case, other mechanism such as VIP node and algorithm are used to facilitate the identification process. We embed object oriented concepts in actual implementation. The experimental results show that our mechanism works successfully and the time used in the identification process reduced significantly.

當今已有數以百萬計的行動應用程序在 Apple 的 App Store 中發布，並在iOS設備下載量超過150億次。為了保護iOS用戶免於惡意應用程式的傷害，Apple 對於上架之App 有相對嚴格的審查政策。通過審查的App才能在App Store中發布。在本文中，我們提出基於 iOS可執行檔的靜態字串分析技術用於檢驗App可能動態載入之類別 。為了檢查動態載入之類別是否符合Apple之規範，必須要能確定動態加載函數之可能字串參數值 。我們方法的第一步是使用現有工具擷取 iOS可執行檔的組合語言。然後自組合語言中建立整個程式的控制流程圖（CFGs） 。接著，在控制流程圖上識別動態加載類別的函數，並且對於該函數的每個參數，我們構造一個字串相依圖，用以顯示流向字串參數值的所有構成成分以及構成方式 。最後，我們對這些可能流向參數的字串進行字串分析，以確定這些參數值所有的可能值集合。透過把這些可能值與特徵值（從Apple 審查政策建構而來，例如私有/敏感性API），我們能夠檢測到App 潛在違背Apple政策之情形。我們分析了1300多種目前上架於App Store的App，並檢查他們是否違反蘋果關於使用私有API的政策以及 廣告識別碼（IDFA）政策。我們的工具提取了超過37000 這些App的字符相依圖，分析結果顯示208個App透過字串操作構組合出對應的API名稱並且有潛在的IDFA違規濫用之可能。我們的分析還發現了372個可以使用字串構建私有類名稱的應用程序和236個可以使用路徑字符串加載私有框架的App，這些App可能違反Apple 禁止使用私有API使用政策。 / Millions of mobile apps have been published in Apple's AppStore with more than 15 billion downloads by iOS devices. In order to protect iOS users from malicious apps, Apple has strict policies which are used to eliminate apps before they can be published in the AppStore. In this paper we present a string analysis technique for iOS executables for statically checking policies that are related to dynamically loaded classes. In order to check that an app conforms to such a policy, it is necessary to determine the possible string values for the class name parameters of the functions that dynamically load classes. The first step of our approach is to construct the assembly for iOS executables using existing tools. We then extract flow information from the assembly code and construct control flow graphs (CFGs) of functions. We identify functions that dynamically load classes, and for each parameter that corresponds to a dynamically loaded class, we construct a dependency graph that shows the set of values that flow to that parameter. Finally, we conduct string analysis on these dependency graphs to determine all potential string values that these parameters can take, which identifies the set of dynamically loaded classes. Taking the intersection of these values with patterns that characterize Apple's app policies (such as private/sensitive APIs), we are able to detect potential policy violations. We analyzed more than 1300 popular apps from Apple's AppStore and checked them against Apple's policy about the use of private APIs and the identifier for Advertising (IDFA). Our tool extracted more than 37000 string dependency graphs from these applications and our analysis reported 208 apps that compose the corresponding API with strings and have potential IDFA violations. Our analysis also found 372 apps that could have compose the private class name with string and 236 apps that could have load the private framework with path string; and could violate the private API usage policy.

本研究利用字串分析之方式對行動應用程式之執行檔進行靜態分析，進以偵測行動應用程式之行為。 本研究計算行動應用程式所呼叫特定系統函式之序列，進一步比對特定可疑行為模式並判定行動應用程式是否包含其可疑行為，由於進行此研究需要考慮行動應用程式執行檔中每一個系統函式的呼叫，因此增加了大量的計算複雜度，故需要大量的運算資源來進行，為了提高運算的效率，本研究採用了Hadoop 作為分散式運算的平台來達成可延展的分析系統，進以達成分析大量行動應用程式的目的，透過建立特定的行為模式庫，本研究已分析了上千個現實使用的行動應用程式，並提供其含有潛在可疑行為的分析報告。 / This work presents a syntax analysis on the executable files of iOS apps to characterize and detect suspicious behaviors performed by the apps. The main idea is counting the appearances of call sequences in the apps which are resolved via reassembling the executable binaries. Since counting the call sequences of the app needs to consider different combinations of every function calls in the app, which significantly increases the complexity of the computing, it takes abundant computing power to bring out our analysis on massive apps on the market, to improve the performance and the effectiveness of our analysis, this work adopted a distributed computing algorithm via Hadoop framework achieving a scalable static syntax analysis which is able to process huge amount of modern apps. We learn the malicious behaviors pattern through comparing the pairs of normal and abnormal app which are identical except on certain behaviors we inserted. By matching the patterns with the call sequences we collected from the public apps, we characterized the behaviors of apps and report the suspicious behaviors carried potential security threats in the apps.