KReSIT Logo Kanwal Rekhi School of Information Technology
IITB Logo
IIT Bombay
 
 Research
 Groups
 Publications
 Current Year
 Previous Year
 Publications Archives
 Projects
 Seminars
 Labs
 Techtalks
 

Home > Research > Publications 

Publications



Notice: Uninitialized string offset: 0 in /home/activities/webteam/web/research/publications/display.php on line 17

Notice: Uninitialized string offset: 0 in /home/activities/webteam/web/research/publications/display.php on line 17

Notice: Uninitialized string offset: 0 in /home/activities/webteam/web/research/publications/display.php on line 17

Notice: Uninitialized string offset: 0 in /home/activities/webteam/web/research/publications/display.php on line 17
TitleA Technique for Parallel Reachability Analysis of Java Programs
ConferenceInternational Conference on Information Technology (CIT)-2000, Bhubaneshwar, India  -   2000
Author(s)Raghuraman Rangarajan  Sridhar Iyer  
AbstractReachability Analysis is an important and well-known tool for the static analysis of concurrent programs and involves the systematic enumeration of all possible global states of program execution. However, it suffers from the problems of exponential space and time complexities. The state explosion problem, i.e. the number of states generated for analysis increases exponentially with the number of concurrent threads of execution, has been tackled effectively by the apportioning technique in the context of concurrent object-oriented programs ~\cite{Iy97}. Apportioning reduces the problem of analysing a whole program into a number of smaller problems of individual and independent analysis of portions of the original program. This partitioning is not merely syntactic, but is also an abstraction of the program. However the time complexity of the analysis still remains exponential. In this paper, a new technique is described that tackles the exponential time complexity of reachability analysis, in the context of Java programs. The state-transition graphs for each thread of execution are generated in parallel and these are subsequently combined to generate the complete state-space from which the reachability graph of the given program is determined. Proofs of safety of the technique and experimental results for the reachability analysis of Java programs are provided.




Printer friendly    Comment
  Copyright © 2004 KReSIT, IIT Bombay. All rights reserved sitemap    
  Kanwal Rekhi School of Information Technology, Indian Institute of Technology Bombay, Powai, Mumbai - 400 076.
+91-22-2576 7901/02. Fax: +91-22-2572 0022
Designed by Kamlesh