The Application of the Concept of Abstraction in Program Analysis and Social Network

摘要

In computer science, the concept of abstraction is a widely used technique. Abstraction constructs a level of complexity where outside environment interacts with the system but the details are suppressed under the interaction level. The main idea behind abstraction is to ignore the unnecessary solutions in the process of solving problems.;In this dissertation, we firstly propose the concept of environment discrimination -- a program behaving differently on different platforms. We formally define environment discrimination leveraging trace equivalence and trace abstraction. By abstracting the non-significant function calls in a pair of traces, we develop an algorithm that is able to detect the environment discrimination behaviors in Android applications. In addition, by combining symbolic execution and abstracted trace, our algorithm finds the contributor of environment discrimination in linear time. The result show that the algorithm and framework we design achieves 97% accuracy.;Secondly, we apply the concept of abstraction to social network analysis. In this research, we propose an efficient algorithm which predicts the geographic location of the public pages. The prediction accuracy is over 90%. In order to study each country's impact on Facebook, we abstract pages and links due to the enormous amount of nodes and edges in the public page graph. The result shows that the usage of public page on Facebook is heavily imbalanced. Meanwhile, we notice that the world is closely connected on Facebook. Finally, the results indicate that Islamic countries are clustered into a separate group.;Finally, we use a different abstraction approach to analyze the public pages that are located in the United States. Instead of applying the voting algorithm, the state of each page is associated with a vector of percentage values. Each value represents the probability this page belongs a particular state. We notice that the public page distribution in the U.S. is more balanced than it in the world. Meanwhile, California and New York are two most "important" states in Facebook. In addition, our research shows that the Democratic Party is more popular on online social network.