Performance-Boosting Sparsification of the IFDS Algorithm with Applications to Taint AnalysisACM SIGSOFT Distinguished Paper Award
The IFDS algorithm can be compute- and memory-intensive for some large programs, often running for a long time(more than expected) or terminating prematurely after some time and/or memory budgets have been exhausted. In the latter case, the corresponding IFDS data-flow analyses may suffer from false negatives and/or false positives. To improve this, we introduce a sparse alternative to the traditional IFDS algorithm. Instead of propagating the data-flow facts across all the program points along the program’s (interprocedural) control flow graph, we propagate every data-flow fact directly to its next possible use points along its own sparse control flow graph constructed on the fly, thus reducing significantly both the time and memory requirements incurred by the traditional IFDS algorithm. In our evaluation, we compare FLOWDROID, a taint analysis performed by using the traditional IFDS algorithm, with our sparse incarnation, SPARSEDROID, on a set of 40 Android apps selected. For the time budget (5 hours) and memory budget(220GB) allocated per app, SPARSEDROID can run every app to completion but FLOWDROID terminates prematurely for 9apps, resulting in an average speedup of 22.0x. This implies that when used as a market-level vetting tool, SPARSEDROID can finish analyzing these 40 apps in 2.13 hours (by issuing 228 leak warnings) while FLOWDROID manages to analyze only 30 apps in the same time period (by issuing only 147 leak warnings).
Tue 12 NovDisplayed time zone: Tijuana, Baja California change
16:00 - 17:40 | SecurityDemonstrations / Research Papers / Journal First Presentations at Hillcrest Chair(s): Julia Rubin University of British Columbia | ||
16:00 20mTalk | Performance-Boosting Sparsification of the IFDS Algorithm with Applications to Taint AnalysisACM SIGSOFT Distinguished Paper Award Research Papers Dongjie He University of New South Wales; Institute of Computing Technology, CAS; University of Chinese Academy of Sciences, Haofeng Li Institute of Computing Technology, CAS; University of Chinese Academy of Sciences, Lei Wang Institute of Computing Technology, Chinese Academy of Science, Haining Meng Institute of Computing Technology, CAS; University of Chinese Academy of Sciences, Hengjie Zheng Institute of Computing Technology, CAS; University of Chinese Academy of Sciences, Jie Liu University of New South Wales, Shuangwei Hu vivo AI Lab, Lian Li Institute of Computing Technology at Chinese Academy of Sciences, China, Jingling Xue UNSW Sydney | ||
16:20 20mTalk | Characterizing Android App Signing Issues Research Papers Haoyu Wang Beijing University of Posts and Telecommunications, China, Hongxuan Liu Peking University, Xusheng Xiao Case Western Reserve University, Guozhu Meng Institute of Information Engineering, Chinese Academy of Sciences, Yao Guo Peking University | ||
16:40 20mTalk | OAuthLint: An Empirical Study on OAuth Bugs in Android Applications Research Papers Tamjid Al Rahat University of Virginia, Yu Feng University of California, Santa Barbara, Yuan Tian University of Virginia Pre-print | ||
17:00 20mTalk | Are Free Android App Security Analysis Tools Effective in Detecting Known Vulnerabilities? Journal First Presentations Link to publication DOI Pre-print Media Attached | ||
17:20 10mDemonstration | SWAN_ASSIST: Semi-Automated Detection of Code-Specific, Security-Relevant Methods Demonstrations Goran Piskachev Fraunhofer IEM, Lisa Nguyen Quang Do Google, Oshando Johnson Fraunhofer IEM, Eric Bodden Heinz Nixdorf Institut, Paderborn University and Fraunhofer IEM Pre-print Media Attached File Attached | ||
17:30 10mDemonstration | Sip4J: Statically Inferring Access Permission Contracts for Parallelising Sequential Java Programs Demonstrations Ayesha Sadiq Monash University, Li Li Monash University, Australia, Yuan-Fang Li Monash University, Ijaz Ahmed University of Lahore, Sea Ling Monash University | ||