Tue 18 Jul 2023 16:00 - 16:10 at Habib Classroom (Gates G01) - ISSTA Online 2: Static Analysis Chair(s): Julian Dolby

The IFDS algorithm can be both memory- and compute-intensive for large programs as it needs to store a huge amount of path edges in memory and process them until a fixed point.
In general, an IFDS-based data-flow analysis, such as taint analysis, aims to discover
only the data-flow facts at some program points. Maintaining a huge amount of path edges (with many visited only once) wastes memory resources, and consequently, reduces its scalability and efficiency (due to frequent re-hashings for the path-edge data structure used).

This paper introduces a fine-grained garbage collection (GC) algorithm to enable (multi-threaded)
IFDS to reduce its memory footprint by removing non-live path edges (i.e., ones that are no longer needed for establishing other path edges) from its path-edge data structure. The resulting IFDS algorithm, named FPC, retains the correctness, precision, and termination properties of IFDS while avoiding re-processing GC'ed path edges redundantly (in the presence of unknown recursive cycles that may be formed in future iterations of the analysis).
Unlike CleanDroid, which augments IFDS with a coarse-grained GC algorithm to collect path edges
at the method level, FPC is fine-grained by collecting path edges at the data-fact level. As a result, FPC can collect more path edges than CleanDroid, and consequently, cause fewer re-hashings for the path-edge data structure used. In our evaluation, we focus on applying an IFDS-based taint analysis to a set of 28 Android apps. FPC can scalably analyze three apps that CleanDroid fails to run to completion (under a 3-hour budget per app) due to out-of-memory (OoM).
For the remaining 25 apps, FPC reduces the number of path edges and memory usage incurred under CleanDroid by 4.4$\times$ and 1.4$\times$ on average, respectively, and consequently, outperforms CleanDroid by 1.7$\times$ on average (with 18.5$\times$ in the best case).

Tue 18 Jul

Displayed time zone: Pacific Time (US & Canada) change

15:30 - 17:00
ISSTA Online 2: Static AnalysisTechnical Papers at Habib Classroom (Gates G01)
Chair(s): Julian Dolby IBM Research
15:30
10m
Talk
Fine-Grained Code Clone Detection with Block-Based Splitting of Abstract Syntax Tree
Technical Papers
Tiancheng Hu Huazhong University of Science and Technology, Zijing Xu Huazhong University of Science and Technology, Yilin Fang Huazhong University of Science and Technology, Yueming Wu Nanyang Technological University, Bin Yuan Huazhong University of Science and Technology, Deqing Zou Huazhong University of Science and Technology, Hai Jin Huazhong University of Science and Technology
DOI
15:40
10m
Talk
Hybrid Inlining: A Framework for Compositional and Context-Sensitive Static Analysis
Technical Papers
Jiangchao Liu Ant Group; ByteDance, Jierui Liu Ant Group, Peng Di Ant Group, Diyu Wu Ant Group, Hengjie Zheng Ant Group, Alex X. Liu Ant Group, Jingling Xue UNSW
DOI
15:50
10m
Talk
CGuard: Scalable and Precise Object Bounds Protection for C
Technical Papers
Piyus Kedia IIIT Delhi, Rahul Purandare University of Nebraska-Lincoln, Udit Kumar Agarwal University of British Columbia, Rishabh GGSIPU
DOI
16:00
10m
Talk
Reducing the Memory Footprint of IFDS-Based Data-Flow Analyses using Fine-Grained Garbage CollectionACM SIGSOFT Distinguished Artifact
Technical Papers
Dongjie He UNSW, Yujiang Gui UNSW, Yaoqing Gao Huawei Toronto Research Center, Jingling Xue UNSW
DOI
16:10
10m
Talk
GenCoG: A DSL-Based Approach to Generating Computation Graphs for TVM Testing
Technical Papers
Zihan Wang Shanghai Jiao Tong University, Pengbo Nie Shanghai Jiao Tong University, Xinyuan Miao Shanghai Jiao Tong University, Yuting Chen Shanghai Jiao Tong University, Chengcheng Wan East China Normal University, Lei Bu Nanjing University, Jianjun Zhao Kyushu University
DOI
16:20
10m
Talk
Splendor: Static Detection of Stored XSS in Modern Web Applications
Technical Papers
He Su Institute of Information Engineering at Chinese Academy of Sciences, Feng Li Institute of Information Engineering at Chinese Academy of Sciences, Lili Xu Institute of Information Engineering at Chinese Academy of Sciences, Wenbo Hu Institute of Information Engineering at Chinese Academy of Sciences, Yujie Sun Institute of Information Engineering at Chinese Academy of Sciences, Qing Sun Institute of Information Engineering at Chinese Academy of Sciences, Huina Chao Institute of Information Engineering at Chinese Academy of Sciences, Wei Huo Institute of Information Engineering at Chinese Academy of Sciences
DOI
16:30
10m
Talk
Improving Bit-Blasting for Nonlinear Integer ConstraintsACM SIGSOFT Distinguished Paper
Technical Papers
Fuqi Jia Institute of Software at Chinese Academy of Sciences; University of Chinese Academy of Sciences, Rui Han Institute of Software at Chinese Academy of Sciences; University of Chinese Academy of Sciences, Pei Huang Stanford University, Minghao Liu Institute of Software at Chinese Academy of Sciences; University of Chinese Academy of Sciences, Feifei Ma Institute of Software at Chinese Academy of Sciences; University of Chinese Academy of Sciences, Jian Zhang Institute of Software at Chinese Academy of Sciences; University of Chinese Academy of Sciences
DOI
16:40
10m
Talk
Loop Invariant Inference through SMT Solving Enhanced Reinforcement Learning
Technical Papers
Shiwen Yu National University of Defense Technology, Ting Wang National University of Defense Technology, Ji Wang National University of Defense Technology
DOI