Browsing by Author "Yang, W"

Now showing 1 - 14 of 14

A classification of noncircular attribute grammars based on the look-ahead behavior
(2002-03-01)
Yang, W
;
資訊工程學系
;
Department of Computer Science
We propose a family of static evaluators for subclasses of the well-defined (i.e., noncircular) attribute grammars. These evaluators augment the evaluator for the absolutely noncircular attribute grammars with look-ahead behaviors. Because this family covers exactly the set of all well-defined attribute grammars, well-defined attribute grammars may be classified into a hierarchy, called the NC hierarchy, according to their evaluators in the family. The location of a noncircular attribute grammar in the NC hierarchy is an intrinsic property of the grammar. The NC hierarchy confirms a result of Riis and Skyum, which says that all well-defined attribute grammars allow a (static) pure multivisit evaluator by actually constructing such an evaluator. We also show that, for any finite m, an NC(m) attribute grammar can be transformed to an equivalent NC(0) grammar.
A finest partitioning algorithm for attribute grammars
(1999-10-01)
Yang, W
;
資訊工程學系
;
Department of Computer Science
The attribute dependence graph of a syntax tree may be partitioned into disjoint regions. Attribute instances in different regions are independent of one other. The advantages of partitioning the attribute dependence graph include simplifying the attribute grammar conceptually and allowing the possibility of parallel evaluation. We present a static partitioning algorithm for attribute grammars. The algorithm builds the set of all feasible partitions for every production by analyzing the grammar. After the attributed syntax tree is constructed, one of the feasible partitions is chosen for each production instance in the syntax tree. Gluing together the selected partitions for individual production instances results in a partition of the attribute dependence graph of the syntax tree. No further merging or partitioning is needed at evaluation time. In addition to static partitioning, the algorithm always produces the finest partition of every attribute dependence graph. An application of the partitioning technique is the strictness analysis for a simple programming language that contains no higher-order functions. (C) 2000 Elsevier Science Ltd. All rights reserved.
A lattice framework for analyzing context-free languages with applications in parser simplification and data-flow analysis
(1999-03-01)
Yang, W
;
資訊工程學系
;
Department of Computer Science
We propose a lattice framework for analyzing context-free grammars and context-free languages. This framework is motivated by a technique for simplifying parsers with information derived from the associated scanners. We define the lattice framework and demonstrate it using additional applications, including data-flow analysis. Soundness and other properties of the lattice framework are also discussed.
Advanced obfuscation techniques for Java bytecode
(2004-04-01)
Chan, JT
;
Yang, W
;
資訊工程學系
;
Department of Computer Science
There exist several obfuscation tools for preventing Java bytecode from being decompiled. Most of these tools simply scramble the names of the identifiers stored in a bytecode by substituting the identifiers with meaningless names. However, the scrambling technique cannot deter a determined cracker very long. We propose several advanced obfuscation techniques that make Java bytecode impossible to recompile or make the decompiled program difficult to understand and to recompile. The crux of our approach is to over use an identifier. That is, an identifier can denote several entities, such as types, fields, and methods, simultaneously. An additional benefit is that the size of the bytecode is reduced because fewer and shorter identifier names are used. Furthermore, we also propose several techniques to intentionally introduce syntactic and semantic errors into the decompiled program while preserving the original behaviors of the bytecode. Thus, the decompiled program would have to be debugged manually. Although our basic approach is to scramble the identifiers in Java bytecode, the scrambled bytecode produced with our techniques is much harder to crack than that produced with other identifier scrambling techniques. Furthermore, the run-time efficiency of the obfuscated bytecode is also improved because the size of the bytecode becomes smaller after obfuscation. (C) 2002 Elsevier Inc. All rights reserved.
Conditional evaluation in simple multi-visit attribute-grammar evaluators
(1997)
Yang, W
;
資訊工程學系
;
Department of Computer Science
Attribute grammars are a formalism for specifying computations on context-free languages. Due to the non-strictness of the if constructs in attribution equations, it is possible to avoid evaluating certain attribute instances in a syntax free. A dynamic evaluator can easily avoid such useless computations with a demand-driven approach. However, dynamic evaluators are not efficient because they need to keep the attribute dependence graph during evaluation, and they need to decide an evaluation order for each syntax tree. In contrast, a visit-oriented (static) evaluator can carefully re-arrange the evaluation order and still avoid unnecessary computations. We propose such a technique in this paper.
Discovering anomalies in access modifiers in Java with a formal specification
(2001-02-01)
Yang, W
;
交大名義發表
;
National Chiao Tung University
The Java programming language provides three access modifiers to control the visibility of the members of a class. Though identifying the weaknesses of the access modifiers from the informal semantics stated in the language manual is difficult, this does not mean that the access modifiers provide a sound ground for building secure programs. A rigorous study of the access modifiers with attribute grammars has uncovered several situations that are irregular or counterintuitive. These situations are confusing to programmers and may create weaknesses in Java programs.
Efficient message flooding on DHT network
(2005)
Huang, CW
;
Yang, W
;
資訊工程學系
;
Department of Computer Science
For the high scalability, DHT network becomes popular in P2P development in these few years. In comparing to flooding-based searching in unstructured P2P network, DHT network provides an efficient lookup. However, flooding still plays an important role in P2P systems. Some fundamental functions such as information collection, dissemination, or keyword searching can benefit from an efficient flooding mechanism. In this paper, we present a DHT network in which one flooding request generates O(N) messages where N is the system size. Moreover, our method considers message locality. Message forwarding across different autonomous systems are reduced significantly. Base on our flooding mechanism, information broadcasting and aggregation are fulfilled without much effort.
Mealy machines are a better model of lexical analyzers
(1996-04-01)
Yang, W
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
;
Department of Computer Science
Lexical analyzers partition input characters into tokens. When ambiguities arise during lexical analysis, the longest-match rule is generally adopted to resolve the ambiguities. The longest-match rule causes the look-ahead problem in traditional lexical analyzers, which are based on Moore machines. In Moore machines, output tokens are associated with stares of the automata. By contrast, because Mealy machines associate output tokens with state transitions, the look-ahead behaviors can be encoded in their state transition tables. Therefore, we believe that lexical analyzers should be based on Mealy machines, rather than Moore machines, in order to solve the look-ahead problem. We propose techniques to construct Mealy machines from regular expressions and to perform sequential and data-parallel lexical analysis with these Mealy machines. Copyright (C) 1996 Elsevier Science Ltd
Multi-plan attribute grammars
(1997)
Yang, W
;
資訊工程學系
;
Department of Computer Science
We identify a new class of non-circular attribute grammars, called the multi-plan attribute grammars, for which static evaluation plans can be computed. The class of multi-plan attribute grammars is larger than all currently known classes of non-circular attribute grammars with static evaluation plans. The decision procedure and the procedure for computing evaluation plans take essentially polynomial time under a new, more practical criterion (but the procedures still take exponential time based on the traditional criterion). The multi-plan attribute grammars lead to a new way to classify well-defined attribute grammars into a hierarchy based on the look-ahead behavior of the evaluators. Our work confirms a result of Riis and Skyum, which says that all well-defined attribute grammars can be evaluated with static evaluators.
On preventing type flaw attacks on security protocols with a simplified tagging scheme
(2005-01-01)
Li, YF
;
Yang, W
;
Huang, CW
;
資訊工程學系
;
Department of Computer Science
A type flaw attack on a security protocol is an attack in which a field in a message that was originally intended to have one type is subsequently interpreted as having another type. Heather et al. proved that type flaw attacks can be prevented by tagging each field with the information that indicates its intended type. We simplify Heather et al.'s tagging scheme by combining all the tags inside each encrypted component into a single tag and by omitting the tags on the outermost level. The simplification process reduces the sizes of messages in the security protocol. We also formally prove that our simplified tagging scheme is as secure as Heather et al.' with the strand space method.
On the applicability of the longest-match rule in lexical analysis
(2002-10-01)
Yang, W
;
Tsay, CW
;
Chan, JT
;
資訊工程學系
;
Department of Computer Science
The lexical analyzer of a compiler usually adopts the longest-match rule to resolve ambiguities when deciding the next token in the input stream. However, that rule may not be applicable in all situations. Because the longest-match rule is widely used, a language designer or a compiler implementor frequently overlooks the subtle implications of the rule. The consequence is either a flawed language design or a deficient implementation. We propose a method that automatically checks the applicability of the longest-match rule and identifies precisely the situations in which that rule is not applicable. The method is useful to both language designers and compiler implementors. In particular, the method is indispensable to automatic generators of language translation systems since, without the method, the generated lexical analyzers can only blindly apply the longest-match rule and this results in erroneous behaviors. The crux of the method consists of two algorithms: one is to compute the regular set of the sequences of tokens produced by a nondeterministic Mealy automaton when the automaton processes elements of an input regular set. The other is to determine whether a regular set and a context-free language have nontrivial intersection with a set of equations. (C) 2002 Elsevier Science Ltd. All rights reserved.
Traps in Java
(2004-06-01)
Chan, JT
;
Yang, W
;
Huang, JW
;
資訊工程學系
;
Department of Computer Science
Though the Java programming language was designed with extreme care, there are still a few ambiguities and irregularities left in the language. The ambiguities are those issues that are not defined clearly in the Java language specification. The different results produced by different compilers on several example programs justify our observations. The irregularities are issues that often confuse programmers. It is hard for a confused programmer to write robust programs. Furthermore, a few issues of the Java language are left intentionally open to the compiler writers. Their effects on Java programs are discussed. The problems of ambiguity, irregularity, and dependence on implementations frequently trap an incautious Java programmer. Some suggestions and solutions for the problems are provided in this paper. (C) 2003 Elsevier Inc. All rights reserved.
Uncovering attacks on security protocols
(2005)
Yang, W
;
交大名義發表
;
National Chiao Tung University
Security protocols are indispensable in secure communication. We give an operational semantics of security protocols in terms of a Prolog-like language. With this semantics, we can uncover attacks on a security protocol that are possible with no more than a given number of rounds. Though our approach is exhaustive testing, the majority of fruitless search is cut off by selecting a small number of representative values that could be sent by an attacker Hence, the number of scenarios is relatively small and our method is quite practical. Furthermore, our method not only reports possible attacks but also describes the attacks in great detail. This description would be very helpful to protocol designers and analyzers.
Why is 1+1=2?
(2002-05-01)
Yang, W
;
資訊工程學系
;
Department of Computer Science
Too often we take the method of decimal addition to be the definition of addition. We clarify this misunderstanding by first giving a definition of addition and then proving that the decimal addition method is both sound and complete with respect to the given definition. By showing the soundness and completeness of decimal addition with respect to the addition of natural numbers, we actually propose a new approach to algorithm correctness. We also discuss the differences between our logic approach and the traditional axiomatic approach.