Abstract
Static analysis has been successfully used in many areas, from verifying mission-critical software to malware detection. Unfortunately, static analysis often produces false positives, which require significant manual effort to resolve. In this paper, we show how to overlay a probabilistic model, trained using domain knowledge, on top of static analysis results, in order to triage static analysis results. We apply this idea to analyzing mobile applications. Android application components can communicate with each other, both within single applications and between different applications. Unfortunately, techniques to statically infer Inter-Component Communication (ICC) yield many potential inter-component and interapplication links, most of which are false positives. At large scales, scrutinizing all potential links is simply not feasible. We therefore overlay a probabilistic model of ICC on top of static analysis results. Since computing the inter-component links is a prerequisite to inter-component analysis, we introduce a formalism for inferring ICC links based on set constraints.We design an efficient algorithm for performing link resolution. We compute all potential links in a corpus of 11, 267 applications in 30 minutes and triage them using our probabilistic approach. We find that over 95.1% of all 636 million potential links are associated with probability values below 0.01 and are thus likely unfeasible links. Thus, it is possible to consider only a small subset of all links without significant loss of information. This work is the first significant step in making static inter-application analysis more tractable, even at large scales.
| Original language | English |
|---|---|
| Title of host publication | POPL'16 - Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages |
| Subtitle of host publication | January 20–22, 2016 St. Petersburg, FL, USA |
| Editors | Rastislav Bodik, Rupak Majumdar |
| Place of Publication | New York NY USA |
| Publisher | Association for Computing Machinery (ACM) |
| Pages | 469-484 |
| Number of pages | 16 |
| ISBN (Electronic) | 9781450335492 |
| DOIs | |
| Publication status | Published - 2016 |
| Externally published | Yes |
| Event | Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages 2016 - St. Petersburg, United States of America Duration: 20 Jan 2016 → 22 Jan 2016 Conference number: 43rd https://popl16.sigplan.org/ |
Conference
| Conference | Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages 2016 |
|---|---|
| Abbreviated title | POPL 2016 |
| Country | United States of America |
| City | St. Petersburg |
| Period | 20/01/16 → 22/01/16 |
| Internet address |
Keywords
- Android ICC
- Inter-component communication
- Probabilistic program analysis
- Static analysis
Cite this
}
Combining static analysis with probabilistic models to enable market-scale android inter-component analysis. / Octeau, Damien; Jha, Somesh; Dering, Matthew; McDaniel, Patrick; Bartel, Alexandre; Li, Li; Klein, Jacques; Traon, Yves Le.
POPL'16 - Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages: January 20–22, 2016 St. Petersburg, FL, USA. ed. / Rastislav Bodik; Rupak Majumdar. New York NY USA : Association for Computing Machinery (ACM), 2016. p. 469-484.Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review
TY - GEN
T1 - Combining static analysis with probabilistic models to enable market-scale android inter-component analysis
AU - Octeau, Damien
AU - Jha, Somesh
AU - Dering, Matthew
AU - McDaniel, Patrick
AU - Bartel, Alexandre
AU - Li, Li
AU - Klein, Jacques
AU - Traon, Yves Le
PY - 2016
Y1 - 2016
N2 - Static analysis has been successfully used in many areas, from verifying mission-critical software to malware detection. Unfortunately, static analysis often produces false positives, which require significant manual effort to resolve. In this paper, we show how to overlay a probabilistic model, trained using domain knowledge, on top of static analysis results, in order to triage static analysis results. We apply this idea to analyzing mobile applications. Android application components can communicate with each other, both within single applications and between different applications. Unfortunately, techniques to statically infer Inter-Component Communication (ICC) yield many potential inter-component and interapplication links, most of which are false positives. At large scales, scrutinizing all potential links is simply not feasible. We therefore overlay a probabilistic model of ICC on top of static analysis results. Since computing the inter-component links is a prerequisite to inter-component analysis, we introduce a formalism for inferring ICC links based on set constraints.We design an efficient algorithm for performing link resolution. We compute all potential links in a corpus of 11, 267 applications in 30 minutes and triage them using our probabilistic approach. We find that over 95.1% of all 636 million potential links are associated with probability values below 0.01 and are thus likely unfeasible links. Thus, it is possible to consider only a small subset of all links without significant loss of information. This work is the first significant step in making static inter-application analysis more tractable, even at large scales.
AB - Static analysis has been successfully used in many areas, from verifying mission-critical software to malware detection. Unfortunately, static analysis often produces false positives, which require significant manual effort to resolve. In this paper, we show how to overlay a probabilistic model, trained using domain knowledge, on top of static analysis results, in order to triage static analysis results. We apply this idea to analyzing mobile applications. Android application components can communicate with each other, both within single applications and between different applications. Unfortunately, techniques to statically infer Inter-Component Communication (ICC) yield many potential inter-component and interapplication links, most of which are false positives. At large scales, scrutinizing all potential links is simply not feasible. We therefore overlay a probabilistic model of ICC on top of static analysis results. Since computing the inter-component links is a prerequisite to inter-component analysis, we introduce a formalism for inferring ICC links based on set constraints.We design an efficient algorithm for performing link resolution. We compute all potential links in a corpus of 11, 267 applications in 30 minutes and triage them using our probabilistic approach. We find that over 95.1% of all 636 million potential links are associated with probability values below 0.01 and are thus likely unfeasible links. Thus, it is possible to consider only a small subset of all links without significant loss of information. This work is the first significant step in making static inter-application analysis more tractable, even at large scales.
KW - Android ICC
KW - Inter-component communication
KW - Probabilistic program analysis
KW - Static analysis
UR - http://www.scopus.com/inward/record.url?scp=84962580740&partnerID=8YFLogxK
U2 - 10.1145/2837614.2837661
DO - 10.1145/2837614.2837661
M3 - Conference Paper
AN - SCOPUS:84962580740
SP - 469
EP - 484
BT - POPL'16 - Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
A2 - Bodik, Rastislav
A2 - Majumdar, Rupak
PB - Association for Computing Machinery (ACM)
CY - New York NY USA
ER -