| Title | Scaling Up the IFDS Algorithm with Efficient Disk-Assisted Computing |
| Publication Type | Conference Paper |
| Year of Publication | 2021 |
| Authors | Li, Haofeng, Meng, Haining, Zheng, Hengjie, Cao, Liqing, Lu, Jie, Li, Lian, Gao, Lin |
| Conference Name | 2021 IEEE/ACM International Symposium on Code Generation and Optimization (CGO) |
| Keywords | composability, IFDS, memory consumption, Memory management, Metrics, Optimization, pubcrawl, Random access memory, Scalability, taint analysis, Tools |
| Abstract | The IFDS algorithm can be memory-intensive, requiring a memory budget of more than 100 GB of RAM for some applications. The large memory requirements significantly restrict the deployment of IFDS-based tools in practise. To improve this, we propose a disk-assisted solution that drastically reduces the memory requirements of traditional IFDS solvers. Our solution saves memory by 1) recomputing instead of memorizing intermediate analysis data, and 2) swapping in-memory data to disk when memory usages reach a threshold. We implement sophisticated scheduling schemes to swap data between memory and disks efficiently. We have developed a new taint analysis tool, DiskDroid, based on our disk-assisted IFDS solver. Compared to FlowDroid, a state-of-the-art IFDS-based taint analysis tool, for a set of 19 apps which take from 10 to 128 GB of RAM by FlowDroid, DiskDroid can analyze them with less than 10GB of RAM at a slight performance improvement of 8.6%. In addition, for 21 apps requiring more than 128GB of RAM by FlowDroid, DiskDroid can analyze each app in 3 hours, under the same memory budget of 10GB. This makes the tool deployable to normal desktop environments. We make the tool publicly available at https://github.com/HaofLi/DiskDroid. |
| DOI | 10.1109/CGO51591.2021.9370311 |
| Citation Key | li_scaling_2021 |
Scaling Up the IFDS Algorithm with Efficient Disk-Assisted Computing