A Linear-Time Complexity Algorithm for Solving the Dyck-CFL Reachability Problem on Bi-directed Trees

被引：0
作者：
Sun Xiaoshan [1 ]
Zhang Yang [2 ]
Cheng Liang [2 ]
机构：
[1] Chinese Acad Sci, Grad Sch, State Key Lab Informat Secur, Beijing 100049, Peoples R China
[2] Chinese Acad Sci, Inst Software, State Key Lab Informat Secur, Beijing 100190, Peoples R China
来源：
FIFTH INTERNATIONAL CONFERENCE ON MACHINE VISION (ICMV 2012): COMPUTER VISION, IMAGE ANALYSIS AND PROCESSING | 2013年 / 8783卷
基金：
中国国家自然科学基金;
关键词：
Dyck-cfl reachability; static program analysis; vulnerability detection; RECURSIVE STATE MACHINES; POINTS-TO ANALYSIS; PUSHDOWN-AUTOMATA; COMMON ANCESTORS; RECOGNITION; !text type='JAVA']JAVA[!/text;
D O I：
10.1117/12.2021187
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
Today many bug detecting tools use static program analysis techniques to discover the vulnerabilities in programs, and many static program analyses can be converted to CFL (Context-Free-Language) reachability problems, most of which are Dyck-CFL reachability problems, a particular class of CFL reachability problems based on Dyck languages. In order to speed up the static analyses formulated using the Dyck-CFL reachability problems, we propose an efficient algorithm of O(n) time for the Dyck-CFL reachability problem when the graph considered is a bidirected tree with specific constraints, while a naive algorithm runs in O(n(2)) time. This is done by the bidirected-tree merging and an efficient method to determine the existence of the directed-path from the source to the destination.
引用
收藏
页数：6
相关论文
共 23 条
[1]   Analysis of recursive state machines [J].
Alur, R ;
Benedikt, M ;
Etessami, K ;
Godefroid, P ;
Reps, T ;
Yannakakis, M .
ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 2005, 27 (04) :786-818
[2]   The LCA problem revisited [J].
Bender, MA ;
Farach-Colton, M .
LATIN 2000: THEORETICAL INFORMATICS, 2000, 1776 :88-94
[3]  
Bouajjani A, 1997, LECT NOTES COMPUT SC, V1243, P135
[4]   Subcubic algorithms for recursive state machines [J].
Chaudhuri, Swarat .
ACM SIGPLAN NOTICES, 2008, 43 (01) :159-169
[5]   FAST ALGORITHMS FOR FINDING NEAREST COMMON ANCESTORS [J].
HAREL, D ;
TARJAN, RE .
SIAM JOURNAL ON COMPUTING, 1984, 13 (02) :338-355
[6]  
HORWITZ S, 1990, ACM T PROGR LANG SYS, V12, P26, DOI 10.1145/960116.53994
[7]  
Hovemeyer D., 2005, ACM SIGSOFT Software Engineering Notes, P13
[8]   The set constraint/CFL reachability connection in practice [J].
Kodumal, J ;
Aiken, A .
ACM SIGPLAN NOTICES, 2004, 39 (06) :207-218
[9]  
Livshits Benjamin, 2006, THESIS
[10]   Interconvertibility of a class of set constraints and context-free-language reachability [J].
Melski, D ;
Reps, T .
THEORETICAL COMPUTER SCIENCE, 2000, 248 (1-2) :29-98
123