| Title: | A linear-time complexity algorithm for solving the dyck-cfl reachability problem on bi-directed trees |
| Author: | Sun, Xiaoshan (1)
; Zhang, Yang (2)
; Cheng, Liang (2)
|
| Conference Name: | 5th International Conference on Machine Vision: Computer Vision, Image Analysis and Processing, ICMV 2012
|
| Conference Date: | October 20, 2012 - October 21, 2012
|
| Issued Date: | 2013
|
| Conference Place: | Wuhan, China
|
| Publish Place: | SPIE, P.O. Box 10, Bellingham, WA 98227-0010, United States
|
| Indexed Type: | EI
|
| ISSN: | 0277786X
|
| ISBN: | 9780819495877
|
| Department: | (1) State Key Laboratory of Information Security, Graduate School of Chinese Academy of Sciences, Beijing 100049, China; (2) State Key Laboratory of Information Security, Institute of Software Chinese Academy of Sciences, Beijing 100190, China
|
| Abstract: | 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 na?ve algorithm runs in O(n2) 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. |
| English Abstract: | 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 na?ve algorithm runs in O(n2) 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. |
| Language: | 英语
|
| Content Type: | 会议论文
|
| URI: | http://ir.iscas.ac.cn/handle/311060/16654
|
| Appears in Collections: | 软件所图书馆_会议论文
|
|
There are no files associated with this item.
|
| Recommended Citation: | |
Sun, Xiaoshan ,Zhang, Yang ,Cheng, Liang . A linear-time complexity algorithm for solving the dyck-cfl reachability problem on bi-directed trees[C]. 见:5th International Conference on Machine Vision: Computer Vision, Image Analysis and Processing, ICMV 2012. Wuhan, China. October 20, 2012 - October 21, 2012.
|
|
|
