Browsing by Author "Yang, Wuu"

Now showing 1 - 20 of 24

A bilateral remote user authentication scheme that preserves user anonymity
(2008-07-01)
Tseng, Huei-Ru
;
Jan, Rong-Hong
;
Yang, Wuu
;
資訊工程學系
;
Department of Computer Science
Smart card-based authentication is one of the most widely used and practical solutions to remote user authentication. Compared to other authentication schemes, our proposed scheme aims to provide more functionalities and to resist well-known attacks. These crucial merits include (1) a user can freely choose and change his passwords; (2) our scheme provides mutual authentication between a server and a user; (3) it achieves user anonymity; (4) a server and a user can generate authenticated sessions keys. Moreover, our scheme can resist replay attacks, forgery attacks, insider attacks, reflection attacks, and parallel session attacks. Copyright (c) 2008 John Wiley & Sons, Ltd.
A Brouwerian Model of the Run-Time Memory
(2015-11-01)
Yang, Wuu
;
資訊工程學系
;
Department of Computer Science
The run-time memory of a program may be described with a directed graph in which nodes represent chunks of memory and edges represent references. We define a closed cluster induced by a node n, denoted as CC(n), as the largest set of nodes that are reachable from n but are unreachable from nodes outside the closed cluster. Based on closed clusters, there is a Brouwerian structure under the run-time memory. We present the Brouwerian model and discuss its properties, transformations, and applications. We also propose a two-counter algorithm for calculating CC(n). The two-counter algorithm is never slower than a traditional one-counter algorithm. Our study of the Brouwerian structure is motivated by work on garbage collection.
A Chaotic Maps-based Key Agreement Protocol that Preserves User Anonymity
(2009)
Tseng, Huei-Ru
;
Jan, Rong-Hong
;
Yang, Wuu
;
資訊工程學系
;
Department of Computer Science
A key agreement protocol is a protocol whereby two or more communicating parties can agree on a key or exchange information over an open communication network in such a way that both of them agree on the established session keys for use in subsequent communications. Recently, several key agreement protocols based on chaotic maps are proposed. These protocols require a verification table to verify the legitimacy of a user. Since this approach clearly incurs the risk of tampering and the cost of managing the table and suffers from the stolen-verifier attack, we propose a novel key agreement protocol based on chaotic maps to enhance the security. The proposed protocol not only achieves mutual authentication without verification tables, but also allows users to anonymously interact with the server. Moreover, security of the proposed protocol is modelled and analyzed with Petri nets. Our analysis shows that the proposed protocol can successfully defend replay attacks, forgery attacks, and stolen-verifier attacks.
A Fast General Parser for Automatic Code Generation
(2010)
Yang, Wuu
;
交大名義發表
;
National Chiao Tung University
The code generator in a compiler attempts to match a subject tree against a collection of tree-shaped patterns for generating instructions. Tree-pattern matching may be considered as a generalization of string parsing. We propose a new generalized LR (GLR) parser, which extends the LR parser stack with a parser cactus. GLR explores all plausible parsing steps to find the least-cost matching. GLR is fast due to two properties: (1) duplicate parsing steps are eliminated and (2) partial parse trees that will not lead to a least-cost matching are discarded as early as possible.(1)
A multiple power-level approach for wireless sensor network positioning
(2008-11-13)
Fang, Jen-Yu
;
Chu, Hung-Chi
;
Jan, Rong-Hong
;
Yang, Wuu
;
資訊工程學系
Wireless sensor networks enhance our ability to monitor the physical world. Many recent researches on wireless sensor networks have focused on aspects such as routing, node cooperation, and energy consumption. In addition to these topics, the positioning service is also an important function in sensor networks. This paper presents a multiple power-level positioning algorithm, discusses its capabilities, and evaluates its performance in various environments. The simulation results show that the proposed algorithm exhibits better accuracy than do traditional single power-level methods. In critical situations such as reference node failure, unstable radio transmission range and beacon collision, the proposed algorithm still performs well. Finally, the positioning method is implemented on a sensor network test bed, and the actual measurements show that, the average estimation error is 2.5 m when three power-levels are used and adjacent reference nodes are 12 m apart in an outdoor environment. (C) 2008 Elsevier B.V. All rights reserved.
A Retargetable Static Binary Translator for the ARM Architecture
(2014-06-01)
Shen, Bor-Yeh
;
Hsu, Wei-Chung
;
Yang, Wuu
;
資訊工程學系
;
Department of Computer Science
Machines designed with new but incompatible Instruction Set Architecture (ISA) may lack proper applications. Binary translation can address this incompatibility by migrating applications from one legacy ISA to a new one, although binary translation has problems such as code discovery for variable-length ISA and code location issues for handling indirect branches. Dynamic Binary Translation (DBT) has been widely adopted for migrating applications since it avoids those problems. Static Binary Translation (SBT) is a less general solution and has not been actively researched. However, SBT performs more aggressive optimizations, which could yield more compact code and better code quality. Applications translated by SBT can consume less memory, processor cycles, and power than DBT and can be started more quickly. These advantages are even more critical for embedded systems than for general systems. In this article, we designed and implemented a new SBT tool, called LLBT, which translates ARM instructions into LLVM IRs and then retargets the LLVM IRs to various ISAs, including x86, x86-64, ARM, and MIPS. LLBT leverages two important functionalities from LLVM: comprehensive optimizations and retargetability. More importantly, LLBT solves the code discovery problem for ARM/Thumb binaries without resorting to interpretation. LLBT also effectively reduced the size of the address mapping table, making SBT a viable solution for embedded systems. Our experiments based on the EEMBC benchmark suite show that the LLBT-generated code can run more than 6x and 2.3x faster on average than emulation with QEMU and HQEMU, respectively.
A robust user authentication scheme with self-certificates for wireless sensor networks
(2011-08-01)
Tseng, Huei-Ru
;
Jan, Rong-Hong
;
Yang, Wuu
;
資訊工程學系
;
Department of Computer Science
User authentication is a critical part of security, along with confidentiality and integrity, for computer systems that allow legitimate users remote access over an open communication network. Recently, user authentication for wireless sensor networks (WSNs) has received considerable attention. We propose a robust user authentication scheme for WSNs. The scheme is based on elliptic-curve cryptosystems with self-certificates. The proposed scheme allows users to change their key pairs without interaction with a key distribution center (KDC). Moreover, the proposed scheme still works well even if the adversary captures t nodes out of n nodes in the WSNs. Security of the proposed scheme is modeled and analyzed with Petri nets. Our analysis shows that the proposed scheme can successfully defend some of the most notorious attacks, including replay attacks, forgery attacks, and node-capture attacks. Copyright (C) 2010 John Wiley & Sons, Ltd.
An improved dynamic user authentication scheme for wireless sensor networks
(2007)
Tseng, Huei-Ru
;
Jan, Rong-Hong
;
Yang, Wuu
;
資訊工程學系
;
Department of Computer Science
Over the last few years, many researchers have paid a lot of attention to the user authentication problem. However, to date, there has been relatively little research suited for wireless sensor networks. Recently, Wong et al. proposed a dynamic user authentication scheme for WSNs that allows legitimate users to query sensor data at every sensor node of the network. We show that Wong et al.'s scheme is vulnerable to the replay and forgery attacks and propose a lightweight dynamic user authentication scheme for WSNs. The proposed scheme not only retains all the advantages in Wong et al.'s scheme but also enhances its security by withstanding the security weaknesses and allows legitimate users to change their passwords freely. In comparison with the previous scheme, our proposed scheme possesses many advantages, including resistance of the replay and forgery attacks, reduction of user's password leakage risk, capability of changeable password, and better efficiency.
Automatic validation for binary translation
(2015-10-01)
Chen, Jiunn-Yeu
;
Yang, Wuu
;
Shen, Bor-Yeh
;
Li, Yuan-Jia
;
Hsu, Wei-Chung
Binary translation is an important technique for porting programs as it allows binary code for one platform to execute on another. It is widely used in virtual machines and emulators. However, implementing a correct (and efficient) binary translator is still very challenging because many delicate details must be handled smartly. Manually identifying mistranslated instructions in an application program is difficult, especially when the application is large. Therefore, automatic validation tools are needed urgently to uncover hidden problems in a binary translator. We developed a new validation tool for binary translators. In our validation tool, the original binary code and the translated binary code run simultaneously. Both versions of the binary code continuously send their architecture states and the stored values, which are the values stored into memory cells, to a third process, the validator. Since most mistranslated instructions will result in wrong architecture states during execution, our validator can catch most mistranslated instructions emitted by a binary translator by comparing the corresponding architecture states. Corresponding architecture states may differ due to (1) translation errors, (2) different (but correct) memory layouts, and (3) return values of certain system calls. The need to differentiate the three sources of differences makes comparing architecture states very difficult, if not impossible. in our validator, we take special care to make memory layouts exactly the same and make the corresponding system calls always return exactly the same values in the original and in the. translated binaries. Therefore, any differences in the corresponding architecture states indicate mistranslated instructions emitted by the binary translator. Besides solving the architecture-state-comparison problems, we also propose several methods to speed up the automatic validation. The first is the validation-block method, which reduces the number of validations while keeping the accuracy of instruction-level validation. The second is quick validation, which provides extremely fast validation at the expense of less accurate error information. Our validator can be applied to different binary translators. In our experiment, the validator has successfully validated programs translated by static, dynamic, and hybrid binary translators. (C) 2015 Elsevier Ltd. All rights reserved.
Broadcasting with the least energy is an NP-complete problem
(2008)
Yang, Wuu
;
Tseng, Huei-Ru
;
Jan, Rong-Hong
;
Shen, Bor-Yeh
;
交大名義發表
Energy conservation is an important issue in wireless networks. We propose a method for estimating the least amount of energy needed for broadcasting a message to all nodes in the network, The method can work with any reasonable energy models. We prove that this least-energy problem is NP-complete by showing that the maximum-leaf spanning-tree problem is a special case of the least-energy problem.
DDoS detection and traceback with decision tree and grey relational analysis
(2011)
Wu, Yi-Chi
;
Tseng, Huei-Ru
;
Yang, Wuu
;
Jan, Rong-Hong
;
資訊工程學系
In Distributed Denial-of-Service (DDoS) Attack, an attacker breaks into many innocent computers (called zombies). Then, the attacker sends a large number of packets from zombies to a server, to prevent the server from conducting normal business operations. We design a DDoS-detection system based on a decision-tree technique and, after detecting an attack, to trace back to the attacker's locations with a traffic-flow pattern-matching technique. Our system could detect DDoS attacks with the false positive ratio about 1.2-2.4%, false negative ratio about 2-10%, and find the attack paths in traceback with the false negative rate 8-12% and false positive rate 12-14%.
DDoS Detection and Traceback with Decision Tree and Grey Relational Analysis
(2009)
Wu, Yi-Chi
;
Tseng, Huei-Ru
;
Yang, Wuu
;
Jan, Rong-Hong
;
資訊工程學系
As modern life becomes increasingly closely bound to the Internet, network security becomes increasingly important. Like it or not, we all live under the shadow of network threats. The threats could cause leakage of privacy and/or economic loss. Among network attacks, the DDoS (distributed denial-of-service) attack is one of the most frequent and serious. In a DDoS attack, an attacker first breaks into many innocent computers (called zombies) by taking advantages of known or unknown bugs and vulnerabilities in the software. Then the attacker sends a large number of packets from these already-captured zombies to a server These packets either occupy a major portion of the server's network bandwidth or they consume much of the server's time. The server is then prevented from conducting normal business operations. In order to mitigate the DDoS threat, we design a system to detect DDoS attacks based on a decision-tree technique and, after detecting an attack, to trace back to the approximate locations of the attacker with a traffic-flow pattern-matching technique. We conduct our experiment on the DETER system. According to our experiment results, our system could detect the DDoS attack with the false positive ratio about 1.2% - 2.4%, false negative ratio about 2% - 10% with different kind of attack, attack sending rate and find the attack path in traceback with the false negative rate 8% - 12% and false positive rate 12% - 14%.(1)
Efficiency and reliability in cluster based peer-to-peer systems
(2006-09-01)
Huang, Ching-Wei
;
Yang, Wuu
;
資訊工程學系
;
Department of Computer Science
Peer-to-peer systems have become one of the most popular Internet applications. Some unstructured systems such Gnutella perform file searching by flooding requests among nodes. It has been proven that such unstructured systems are not scalable, and searching consumes tremendous bandwidth. We propose three mechanisms to reconstruct the system topology and improve message flooding. Our research addresses four aspects: system topology control, message routing, message locality, and system connectedness. The simulation shows that significant redundancy in flooding of messages can be eliminated and message locality achieves a high ratio.
Extended LALR(1) Parsing
(2017-01-01)
Yang, Wuu
;
資訊工程學系
;
Department of Computer Science
We identify a class of context-free grammars, called the extended LALR(1) (ELALR(1)), which is a superclass of LALR(1) and a subclass of LR(1). Our algorithm is essentially a smarter method for merging similar states in the LR(1) state machines. LALR(1) would merge every pair of similar states. In contrast, our algorithm merges a pair of similar states only if no (reduce-reduce) conflicts will be created. Thus, when no conflicts occur, our algorithm produces exactly the same state machines as the LALR(1) algorithm. However, when the LALR(1) algorithm reports conflicts, our algorithm may still produce a (larger) conflict-free state machine. In the extreme case when no states can be merged, our algorithm simply returns the original LR(1) machines. An important characteristic of the ELALR(1) algorithm is that there is no backtracking. On the other hand, the ELALR(1) algorithm does not guarantee the minimum state machines.
HEAP GARBAGE COLLECTION WITH REFERENCE COUNTING
(2010)
Yang, Wuu
;
Tseng, Huei-Ru
;
Jan, Rong-Hong
;
資訊工程學系
;
Department of Computer Science
In algorithms based on reference counting, a garbage-collection decision has to be made whenever a pointer x -> y is about to be destroyed. At this time, the node y may become dead even if y\'s reference count is not zero. This is because y may belong to a piece of cyclic garbage. Some aggressive collection algorithms will put y on the list of potential garbage regardless of y\'s reference count. Later a trace procedure starting from y will be initiated. Other algorithms, less aggressive, will put y on the list of potential garbage only if y\'s reference count falls below a threshold, such as 3. The former approach may waste time on tracing live nodes and the latter may leave cyclic garbage uncollected indefinitely. The problem with the above two approaches (and with reference counting in general) is that it is difficult to decide if y is dead when the pointer x -> y is destroyed. We propose a new garbage-collection algorithm in which each node maintains two, rather than one, reference counters, gcount and hcount. Gcount is the number of references from the global variables and from the run-time stack. Hcount is the number of references from the heap. Our algorithm will put node y on the list of potential garbage if and only if y\'s gcount becomes 0. The better prediction made by our algorithm results in more efficient garbage collectors.
LLBT: An LLVM-based Static Binary Translator
(2012)
Shen, Bor-Yeh
;
Chen, Jiunn-Yeu
;
Hsu, Wei-Chung
;
Yang, Wuu
;
交大名義發表
Lack of applications has always been a serious concern for designing machines with a new but incompatible ISA. To address this concern, binary translation is one common technique to migrate applications from one legacy ISA to new ones. In the past, dynamic binary translation (DBT) has been more widely adopted for migrating applications since it avoids some challenging problems for binary translation such as code discovery for variable length ISA and code location issues for handling indirect branches. Static binary translation (SBT) is usually regarded as a less general solution and has not been actively researched on. However, SBT has advantages of performing more aggressive optimizations, which could yield more compact code and greater code quality. In general, SBT translated applications are likely to consume less memory, processor cycles and power, and can be started more quickly. All the above advantages are more critical for embedded systems than for general systems. Therefore, we believe that even though SBT is not as general as DBT, it has a unique role to play for migrating applications in embedded systems. In this paper, we designed and implemented a new portable SBT tool, called LLBT, which translates source binary into LLVM IR and then retargets the LLVM IR to various ISAs by using the LLVM compiler infrastructure. Using the LLVM compiler infrastructure, LLBT successfully leverages two important functionalities from LLVM: the comprehensive optimizations and the retargetability. For example, most DBTs map guest architecture states into the host registers to minimize accessing guest architecture states with memory operations, but must deal with guest architecture state saving/reloading at trace/block entry/exit points. LLBT can treat the complete application binary as a single function and uses the global register allocation optimization in LLVM to consistently map guest architecture states in host registers so as to avoid the costly state saving and reloading at trace/block exits. In this paper, we have shown our ARM-based LLBT can effectively migrate EEMBC benchmark Suite from ARMv5 to Intel IA32, Intel x64, MIPS, and other ARMs such as ARMv7. On the Intel i7 based host systems, the LLBT generated code can run 3 to 64 times faster than emulating with QEMU, which uses the DBT technique.
On Static Binary Translation of ARM/Thumb Mixed ISA Binaries
(2017-07-01)
Chen, Jiunn-Yeu
;
Yang, Wuu
;
Hsu, Wei-Chung
;
Shen, Bor-Yeh
;
Ou, Quan-Huei
Code discovery has been a main challenge for static binary translation, especially when the source instruction set architecture has variable-length instructions, such as the x86 architectures. Due to embedded data such as PC (program counter)-relative data, jump tables, or paddings in the code section, a binary translator may be misled to translate data as instructions. For variable-length instructions, once a piece of data is mis-translated as instructions, decoding subsequent bytes could also go wrong. We are concerned with static binary translation for the very popular Advanced RISC Machine (ARM) architectures. Although ARM is considered a reduced instruction set computer architecture, it does allow the mix of 32-bit (ARM) instructions and 16-bit (Thumb) instructions in the same executables. In addition to different instruction lengths, the ARM and Thumb instructions are located at 4-byte or 2-byte aligned addresses, respectively. Furthermore, because ARM and Thumb instructions share the same encoding space, a 4-byte word could sometimes be decoded as one ARM instruction or two Thumb instructions. The correct decoding of this 4-byte word is actually determined at runtime by the least-significant bit of the program counter. For unstripped binaries, the mapping symbols can be used to identify ARM code regions and Thumb code regions. However, for stripped binaries, such mapping symbols are unavailable. We propose a novel solution to statically translate stripped ARM/Thumb mixed executables. Our solution is implemented in a static binary translator. The binary translator further generates multiple versions of translated code for the code regions whose types cannot be determined with our solution. One of the code versions is selected during runtime. The binary translator also includes a series of analyses that enable the removal of most useless code versions. Based on the experimental results on stripped ARM/Thumb mixed binaries in the SPEC2006 and Embedded Microprocessor Benchmark Consortium (EEMBC) benchmark suites, our static binary translator achieves impressive performance when migrating them to run on x86 machines and the space overhead is no more than 10%.
On the And-Or-Scheduling Problems
(2014)
Yang, Wuu
;
Huang, Ming-Hsiang
;
Lee, Jenq-Kuen
;
資訊工程學系
;
Department of Computer Science
In the and-or scheduling model, a project consists of several tasks. Each task has a duration attribute. A task can be performed only when all of its requirements are satisfied. After a task is completed, more requirements become satisfied. A characteristic of the AOscheduling projects is that a requirement may be satisfied in several ways. Several questions concerning AOscheduling might be interesting, including whether the project can be completed, the earliest time a project can be completed, the minimal number of processors needed to complete the project, and assigning tasks to processors, etc. We use Petri nets and segment graphs to analyze AOscheduling projects.
Partial Flattening: A Compilation Technique for Irregular Nested Parallelism on GPGPUs
(2016)
Huang, Ming-Hsiang
;
Yang, Wuu
;
交大名義發表
;
National Chiao Tung University
Supporting irregular nested parallelism on modern GPUs requires much effort. One should distribute the parallel tasks evenly while preserving reasonable memory usage. Moreover, the task distribution should also fit the thread hierarchy of the underlying GPU to fully exploit its computing power. We propose partial flattening, an automatic code transformation which translates annotated C programs to CUDA kernels. Thread blocks are treated as flat SIMT processors. Iterations are dynamically organized into batches. Batches are executed in a sequential (depth-first) order. A kernel is treated as multiple independent SIMT processors with an additional task-stealing mechanism. Partial flattening allows easy expression of nested parallelism and synchronization by annotating nested parallel loops or parallel-recursive calls, while preserving reasonable memory usage by the depth-first execution order. Our 2-level task distribution scheme does not need special hardware support, and fits well with the CUDA thread hierarchy. Experiments show that partial flattening outperforms NESL significantly in most benchmarks, and obtains 2.15x and 67x speedup over CUDA dynamic parallelism in Quicksort and the Bron-Kerbosch algorithm, respectively.
PFACC: An OpenACC-like programming model for irregular nested parallelism
(1970-01-01)
Huang, Ming Hsiang
;
Yang, Wuu
;
資訊工程學系
;
Department of Computer Science
OpenACC is a directive-based programming model which allows programmers to write graphic processing unit (GPU) programs by simply annotating parallel loops. However, OpenACC has poor support for irregular nested parallel loops, which are natural choices to express nested parallelism. We propose PFACC, a programming model similar to OpenACC. PFACC directives can be used to annotate parallel loops and to guide data movement between different levels of memory hierarchy. Parallel loops can be arbitrarily nested or be placed inside functions that would be (possibly recursively) called in other parallel loops. The PFACC translator translates C programs with PFACC directives into CUDA programs by inserting runtime iteration-sharing and memory allocation routines. The PFACC runtime iteration-sharing routine is a two-level mechanism. Thread blocks dynamically organize loop iterations intobatchesand execute the batches in a depth-first order. Different thread blocks share iterations among one another with an iteration-stealing mechanism. PFACC generates CUDA programs with reasonable memory usage because of the depth-first execution order. The two-level iteration-sharing mechanism is implemented purely in software and fits well with the CUDA thread hierarchy. Experiments show that PFACC outperforms CUDA dynamic parallelism in terms of performance and code size on most benchmarks.