JAIST Repository >
School of Information Science >
JAIST Research Reports >
Research Report - School of Information Science : ISSN 0918-7553 >
IS-RR-2011 >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10119/9813
|
Title: | Modular Stacking-based Context-Sensitive Program Analysis |
Authors: | Li, Xin Ogawa, Mizuhito |
Issue Date: | 2011-06-29 |
Publisher: | 北陸先端科学技術大学院大学情報科学研究科 |
Magazine name: | Research report (School of Information Science, Japan Advanced Institute of Science and Technology) |
Volume: | IS-RR-2011-002 |
Start page: | 1 |
End page: | 22 |
Abstract: | This paper presents a systematic approach to scaling stackingbased context-sensitive program analysis yielded by weighted pushdown systems, and demonstrates its effectiveness by applications to Java pointsto analysis. Our approach relies on the view offormulating stacking-based analysis as AGPs (abstract grammar problem), and reducing the analysis problem to fixed-point calculation over the equation system encoded by grammar productions. To characterize points-to analysis that does notassume an existing program control flow, we propose Contracted AGP, and a symbolic sliding-window based algorithm for it. The algorithm aimsat reducing both time and memory costs, and its correctness is proved in terms of chaotic iteration. Finally, we instantiated the algorithm within Japot, a context-sensitive points-to analyzer for Java. Experiments show two-fold benefits of our approach in practice, with (i) scaling Japot toDacapo benchmark suite, and (ii) a speed-up of 3x faster in average, given an adjustable memory budget. |
URI: | http://hdl.handle.net/10119/9813 |
Material Type: | publisher |
Appears in Collections: | IS-RR-2011
|
Files in This Item:
File |
Description |
Size | Format |
IS-RR-2011-002.pdf | | 1975Kb | Adobe PDF | View/Open |
|
All items in DSpace are protected by copyright, with all rights reserved.
|