Efficent signature file methods for information retrieval

Yoo, Jae-soo Korea Advanced Institute of Science and Technology 1995 국내박사

Signature of surface bundles over surfaces and mapping class group

이주아 서울대학교 대학원 2017 국내박사

In this thesis, we study the topological constraints on the signature and the Euler characteristic (σ(X); e(X)) for smooth 4-manifolds X (or complex surfaces X) which are surface bundles over surfaces with nonzero signature. The first main result is about the improved upper bounds for the minimal base genus function b(f;n) for a fixed fiber genus f and a fixed signature 4n. In particular, we construct new smooth 4-manifolds with a fixed signature 4 and small Euler characteristic which are surface bundles over surfaces by subtraction of Lefschetz fibrations. They include an example with the smallest Euler characteristic among known examples with non-zero signature. Secondly, we explore possibilities to construct Kodaira fibrations with small signature which are smooth surface bundles over surfaces as ramified coverings of products of two complex curves. To obtain the minimal base genus and the smallest possible signature, we investigate the action of the monodromy of the fibration of pointed curves. Throughout the paper we’ll see that the surface mapping class group plays an important role in both constructions and the control of topological invariants.

Topic Signature와 동시 출현 단어 쌍을 이용한 문서 범주화

배원식 창원대학교 2009 국내석사

We describe a new feature selection method for text categorization system using Topic Signature and co-occurrence words. Co-occurrence word is a pair of words to occur within a window in same documents. We use co-occurred words to classify documents instead of a single word, because we hypothesize that co-occurred words have high ability to classify documents for unique meaning. We use Topic Signature as a feature selection method based log-likelihood ratio. Topic Signature was applied for finding topic words in text summarization. In order to archive a high performance, we use TF-Topic Signature and weight of features to occur in within titles. And we use Naive Bayesian classifier for text classification. We use Reuters-21578 data collection, a standard data collection for evaluating English text categorization system, for evaluating proposed system. We can compare objectively between the proposed system and the previous systems from the data collection. For the result of experiments, we can see that the proposed system give a good performance, when compare the previous systems. The proposed system has some weak point that make many features by using co-occurrence word feature generation. Focus of our future works is to solve the weak points. But we give a good possibility with proposed method, so we expect that our research result is contributed to feature research. 본 논문에서는 Topic Signature와 동시 출현 단어 쌍 자질을 이용한 새로운 문서 범주화 방법에 대하여 기술한다. 동시 출현 단어 쌍은 한 문서에서 일정한 크기의 윈도우 내에 속하는 단어의 쌍으로 정의된다. 본 논문에서는 단어 하나보다 단어의 쌍이 문서의 범주를 판단하는데 더 좋은 자질로 사용될 수 있을 것이라고 가정하였다. 일반적으로 단어 하나는 여러 의미로 사용될 수 있으므로 여러 범주에서 나타날 가능성이 있다. 그러나 단어 쌍은 특별한 의미로 한정되어 특정한 범주에서만 나타날 가능성이 높아지기 때문이다. 자질 추출 방법으로는 Log-likelihood ratio를 기반으로 하는 Topic Signature를 사용한다. Topic Signature는 문서 요약 분야에서 문서의 핵심 단어를 찾기 위해 사용되었던 방법으로, 문서 범주화에서 사용하는 데는 몇 가지 약점을 가지고 있다. 본 논문에서는 이러한 약점을 보완하기 위하여 TF-Topic Signature와 제목에 나타난 자질에 대한 가중치를 부여하는 방법을 사용한다. 그리고 베이지언 분류기(Naive Bayesian Classifier)를 사용하여 문서를 분류한다. 본 논문의 성능 평가에는 Reuters-21578 문서 집합을 사용한다. Reuters-21578 문서 집합은 영어 문서 범주화 시스템 성능 평가의 표준 문서 집합으로 많은 기존 연구에 많이 사용되어 왔다. 따라서 제안 시스템과 기존 시스템을 객관적으로 비교할 수 있다. 실험을 통해 살펴본 결과 기존 시스템과 비교했을 때 좋은 성능을 보였다. 제안 시스템은 동시 출현 단어 쌍 자질을 사용하기 때문에 너무 많은 자질을 생성됨으로 인한 몇 가지 문제점을 안고 있다. 이들 문제점은 향후 연구를 통해 보완해야할 사항이다. 본 논문에서 제안한 방법들은 문서 범주화 시스템에서의 가능성을 충분히 보고 있으므로 앞으로의 연구에도 기여할 수 있을 것이라 기대한다.

Efficient Signature-Based Indexing Schemes for Query Processing in Object-Oriented Database Systems : 객체 지향 데이터베이스에서 질의 처리를 위한 효율적인 시그니쳐 기반의 색인 구조

신학진 전북대학교 대학원 1998 국내박사

객체 지향 데이터베이스 시스템에서 효율적인 질의 처리나 색인 방식의 구현은 객체 지향 데이터베이스 시스템의 성공을 위해서 중요한 문제이다. 특별히 복합 객체(composite objects)는 클래스간에 참조 관계를 가지며, 집단화 계층(aggregation hierarchy)를 형성하기 때문에 질의 처리 시 내포된 객체(nested objects)를 접근하기 위해 매우 큰 순행( traversal)비용을 요구한다. 이와 같은 순행 비용을 최소화하기 위해 다양한 연구가 진행 되었다. 근래에 들어서 소개된 경로 사전 구조는 참조 관계를 나타내는 S-표현(S-expression)을 이용하여 객체간의 순행 시간을 최소로 하고, 다양한 형태의 질의를 효과적으로 처리한다는 장점을 가지고 있다. 하지만 질의 처리 시 데이터베이스를 순차적으로 검색해야 하는 문제점과 경로 사전 역시 순차적 접근을 하는 문제가 있다. 위에서 지적한 복합 객체의 질의 처리 시 요구되는 순연 비용을 최소화하고, 이를 위해 사용하는 경로 사전의 문체를 극복하기 위해서 본 논문에서는 다음과 같이 시그니쳐를 기반한 효과적이고 새로운 색인 구조를 설계한다. 첫째, 경로 사전을 이용하면서 시그니쳐의 중첩(superimpose)방식을 이용한 시그니쳐 파일 기법을 설계한다. 이 시그니쳐를 S-시그니쳐라고 부른다. S-시그니쳐는 경로 사전에 있는 각각의 S-표현식 안에 있는 객체 식별자를 이용하여 객체를 검색한 뒤, 각 객체의 속성 값을 해시(Hash)함수에 대입하여 객체 시그니쳐를 생성한 뒤 이들을 중첩하여 S-시그니쳐를 생성한다. 이와 같은 S-시그니쳐는 경로 사전에 있는 S-표현식과 1:1로 연계하여 참조 공유가 빈번한 상황에서 효과적으로 검색을 수행하고, 특별히 복수개의 질의 조건(predicate)을 가지는 상황에서는 대단히 효과적이다. 둘째, 경로 사전을 이용하면서 시그니쳐의 합성(concatenation)기법을 이용하는 기법을 설계한다. 이 시그니쳐를 우리는 C-시그니쳐라고 부른다. C-시그니쳐에서는 시그니쳐를 이용하여 S-표현식을 필터한 후에도 객체 식별자의 정보를 잃지 않고, S-표현식 안에서 단일 목표 객체 식별자를 필터하는 기능을 가진 구조를 가진다. 이 구조는 임의의 속성에 주어지는 질의 조건을 이용하여 효과적으로 S-표현식을 필터할 수 있고, 필터 된 S-표현을 이용하여 최저의 비용으로 복합 객체 사이를 순행할 수 있도록 한다. 따라서, 복합 객체에 대한 임의의 질의 처리를 효과적으로 수행할 수 있는 접근 기법이며, 이는 복합 객체의 질의 처리에서 필수적인 기술이다. 이상에서 제안한 두 가지 기법과 기존의 관련된 연구들을 구현하여 성능 평가했다. 기존의 접근 기법으로는 경로 색인(path index), 경로 시그니쳐(path signature), 클래스 단위 시그니쳐(class unit signature), 경로 사전(path dictionary), 경로 사전 색인(path dictionary index)을 포함했다. 각각의 접근 기법은 200,000 객체를 포함하는 4개의 클래스와 100,000 객체를 포함하는 6개의 클래스를 가지는 데이터베이스를 대상으로 각각 8가지와 48 가지의 다른 종류의 질의를 주어 성능을 실험했다. 그 결과는 C-시그니쳐가 거의 모든 형태의 검색 질의에서 가장 우수한 성능을 보였다. 또한 여러 개의 질의 조건이 주어질 때, 집단화 계층에서 질의 조건의 위치가 검색 성능에 중요한 변수가 되는 것이 확인 되었고, 이는 질의의 최적화에 중요한 고려 사항이 되겠다. 경로 사전 색인은 질의 조건이 색인 키를 이용하여 진술된 경우에 우수한 검색 성능을 보이고 있다. 끝으로 논문은 이상의 결과 외에 실험 결과를 분석, 비교하여 복합 객체를 포함하는 객체 지향 데이터베이스를 위한 색인 기법의 선택 지침을 제시했다.

Partitioned Parallel Signature File Methods for Information Retrieval : 정보검색을 위한 분할 병렬 요약화일 기법

김정기 전북대학교 대학원 1998 국내박사

컴퓨터의 사용 범위가 넓어짐에 따라, 데이타 관리 및 검색은 오랜 기간 동안 컴퓨터 시스템의 중요한 부분이 되었다. 이것은 데이타베이스관리 시스템(DBMS)이 빠르게 개발되고 널리 사용되는 것으로부터 알 수 있다. 그러나, 전통적인 DBMS는 정형화된 데이타를 처리하기 위해 주로 개발되었으며, 이러한 제한 때문에 텍스트, 이미지, 비디오, 오디오 등의 멀티미디어 데이타를 포함하는 의학 정보 시스템, 사무 정보 시스템, CAD/CAM 시스템, VOD(video-on-demand) 시스템 등의 응용 분야에 부적합하였다. 이러 한 멀티미디어 데이타를 다루기 위하여 요약화일(signature file) 기법이 제안되었고, 이러한 요약화일 기법은 멀티미디어 데이타의 동적인 저장구조를 다루기 적합하므로 삽입, 삭제, 검색을 효율적으로 수행할 수 있다. 요약화일 기법은 정형화된 데이타 뿐만 아니라 비정형의 데이타를 다루기 위한 효울적인 색인 기법으로 알려져 있다. 요약화일은 문서(레코드)의 축약을 담고 있으므로 질의(query) 처리를 위한 필터(filter)로서 동작한다. 여기서, 요약이란 문서 화일로부터 추출된 색인어들을 해싱하여 만든 비트 스트링(bit string)이다. 이러한 요약화일 기법은 부가 저장공간이 원래 데이타 화일의 10~20%로 매우 적고, 다중 단어에 대한 질의와 부분 단어에 대한 질의가 가능하다는 등의 장점이 있다. 그러나, 요약화일 기법은 트리(tree) 구조의 색인 기법인 역화일보다 검색성능이 낮다는 단점이 있다. 그러므로, 요약화일 기법의 검색 성능 개선에 관한 연구가 필요하며, 이를 위해 병렬 요약화일 기법이 제안되었다. 요약화일의 구조상 이를 병렬처리하기에 적합하며, 본 논문에서는 신장해싱(extendable hashing)과 프레 임 슬라이스(frame-slicing) 방법에 근거한 수평 분할 병렬 요약화일 기법 (Horizontally-divided Parallel Signature File, HPSF)과 수직 분할 병렬 요약화일 기법 (Vertically-partitioned Parallel Signature File, VPSF)을 제안한다. 제안하는 기법들은 신장해싱에 의해 동적인 구조를 잘 지원할 수 있으며, 프레임 슬라이스방법에 의해 요약 화일의 필터링 효과를 증가시킬 수 있다. HPSF에서는 프레임 요약의 검색 순서(searching order)를 최대로 이용하기 위하여 수평 병렬화를 이용하고, VPSF에서는 데이타베이스의 레코드 크기가 균일할 때 좋은 검색 성능을 이루기 위하여 수직 병렬화를 이용한다. 또한, HPSF의 수평 병렬에서 요약을프로세싱 노드에 고르게 분포시키기 위하여 경험적 할당방법을 제안한다. VPSF에서는 프레임을 병렬 처리함으로써 프로세싱 노드에 대한 데이타 분할 및 편중 문제를 피할 수 있지만, 프레임 요약의 검색순서를 이용 할 수 없다는 단점이 있다. 아울러, 본 논문에서는 제안된 HPSF와 VPSF의 효율성을 보이기 위해 분석모델을 제시하고, 분석모델에 근거하여 성능평가를 실시한다. 또한, 실제적인 데이타를 가지고 제안된 기법과 기존의 병렬 요약화일 기법인 CAT, FSF, HF의 성능을 실험을 통해 비교한다. 평가하는 항목은 검색시간, 삽입시간, 부가 저장공간 등이다. 실험결과로부터 제안된 기법이 검색성능 면에서 기존의 기법보다 40~60% 효율적임을 보인다. 삽입시간과 삭제시간에서 VPSF가 다른 기법에 비해 30~100% 까지 효율적임을 보인다. 또한, 여러 가지 레코드분포에 따른 성능을 평가하기 위하여 레코드분포의 표준편차를 반으로 줄인 반 정규분포와 두 배로 늘린 배 정규분포에 대하여 성능을 평가한다. 배 정규분포를 가진 레코드 접합에서 HPSF는 HF와 VPSF보다 약 50~70% 좋은 검색성능을 보인다. 반면에, 반 정규분포에서는 VPSF 가 HF나 HPSF보다 20~40% 좋은 검색성능을 보인다. 마지막으로, 본 논문에서는 주어진 환경에 대해 가장 효율적인 병렬 요약화일 기법을 선택하기 위한 선택지침을 제시한다. 일반적으로, 레코드당 색인어의 개수에 대한 편차가 클수록, HPSF는 VPSF와 다른 기존의 방법 보다 좋은 검색성능을 보인다. 반대인 경우, VPSF는 HPSF와 다른 기존의 방법보다 좋은 검색성능을 보인다. 그리고 데이타베이스 크기가 클수록 VPSF가 더 좋은 성능을 보인다. As the usage of computer systems is widespread, data management and retrieval has been a major field of computer systems for a long time. This is evident from the rapid development and widespread use of database management systems (DBMS). However, the conventional DBMS has mainly developed to process formatted data. The limitation has hindered the DBMS from dealing with new applications that have a large amount of unformatted multimedia data, such as text, image, video, and audio. Such applications include medical information systems, office information systems, CAD/CAM systems, VOD(video-on-demand) systems, and a variety of multimedia applications. To deal with them, a signature file method has been proposed so that it may handle documents (or records) containing the multimedia data. According to the characteristic that multimedia data is frequently changed, the new applications demand a dynamic storage structure which effectively supports not only retrieval operations but also insertion, deletion, and updates operations. The signature file method has been widely advocated as an efficient index scheme to handle applications demanding a large amount of unformatted data as well as formatted data. The signature file is an abstraction of documents which acts as a filter to reduce the number of records accessed for a query. And, the signature is a bit string which is generated from terms of a record in order to index the document file. An additional storage space of the signature file method is about 10~20% of the original data file. Even though the signature file method typically provides several advantages, it has a main disadvantage that its retrieval performance is lower than that of the inversion method. Therefore, the retrieval improvement of the signature file method remains to be studied. The signature file method is well suited to the concept of parallelism introduced with the development of a massively parallel machine architecture. In order to improve the retrieval performance, we, in this thesis, propose new parallel signature file methods based on an extendable hashing technique and a frame-sliced signature file: Horizontally-divided Parallel Signature File (HPSF) and Vertically-partitioned Parallel Signature File (VPSF). According to extendable hashing technique, our new method is a dynamic organization for the signature file in parallel environments. In addition, based on the frame slicing technique, we can increase a filtering effect of the signature file. We adapt a horizontal parallelism to the HPSF for maximizing the usage of searching order on frame-sliced signatures and a vertical parallelism to the VPSF for improving the retrieval time when the record size is uniform in database. Due to the horizontal parallelism of the HPSF, we also propose a heuristic processor allocation scheme which efficiently distributes both descriptor keys of the extendable hashing and its frame group in a uniform way. In the VPSF, we treat the frame-sliced signatures in parallel. Therefore, the VPSF can avoid the distribution problem to assign the descriptor key and its signatures. However, the VPSF cannot utilize the searching order of the frames. To show the efficiency of the HPSF and VPSF, we develop analytic cost models and evaluate the performance of our methods based on the cost models. We also run experiments using real data and compare their performance with those of the conventional parallel signature file methods, i.e., CAT, FSF, HF, in terms of retrieval time, storage overhead, and insertion time. The experimental result shows that our methods achieves about 40~60% better retrieval performance than the conventional methods. In addition, we evaluate the performance of our methods on several normal distributions with half and double standard deviations of the real data. From the experimental results on record sets with double standard deviation, we show that our HPSF gains about 50~70% improvement in retrieval time, compared with the HF and the VPSF. Also, on record sets with half standard deviation, the VPSF gains about 20~40% improvement in retrieval time, compared with the HF and the HPSF. In the experiment of insertion time, the VPSF shows the better performance. Finally, we provide a selection guideline to find the most effective parallel signature file method according to the given environments. In general, when the number of terms per records is distributed widely on the database, the HPSF outperforms the VPSF and the conventional methods on retrieval time; and when the number of terms per records is distributed narrowly, the VPSF outperforms the VPSF and the conventional methods.

Multiple point signature를 이용한 3차원 얼굴인식

이동주 연세대학교 대학원 2007 국내석사

In this dissertation, we propose a distinctive facial feature for a pose invariant 3D face recognition method using Multiple Point Signature. We acquire 3D face models using the different devices and input faces which include different poses. All data must be preprocessed and normalized using EC-SVD. We extract the invariant facial feature point using shape indexes and depth values from the range image. We propose a Multiple Point Signature method for measuring global facial surface information. A Multiple Point Signature represents several one-dimensional signatures. This method may not use error tolerance band to deal with noisy data and a registration technique to matching signatures. In addition, it is invariant to translation and rotation. Derivatives of facial surface are not required. Due to these characteristic, a Multiple Point Signature is fast and efficient to describe global information of facial surface. We use Euclidean distance matching for face recognition. We compared the proposed method with a single point signature method. From the experimental results, we have 94.6% recognition rate for the minimum distance matching, 85.4% by a single point signature. The proposed method shows 9.2% higher recognition rate than the single point signature. 본 논문은 3차원 얼굴 인식 방법에 관한 것으로, 3차원 얼굴 인식에 적합한 전역적 특징을 추출하는 Multiple Point Signature를 이용한 3차원 얼굴 인식 방법을 제안하였다. 3차원 얼굴 데이터의 경우 정규화를 통하여 데이터베이스와 같은 공간상에 놓이도록 하고, 얼굴 포즈 변화를 보정하기 위해 오류 보상 특이치 분해(EC-SVD)방식을 사용한다.3차원 레이저 스캐너로 획득된 3차원 얼굴 데이터는 얼굴의 구조적 정보를 이용하여 데이터 정규화 과정을 수행한다. 이렇게 정규화된 3차원 얼굴 데이터로부터 깊이 정보와 표면곡률지수(shape index)를 이용하여 얼굴의 구조적 정보를 알아내고, Multiple Point Signature를 적용시켜 얼굴의 전역적 특징을 나타내는 특징점 정보를 추출한다. 이 특징점 정보들을 3차원 얼굴 데이터베이스로 구성한다. 구조적 조명 방식의 얼굴 획득 장비에 의한 입력 영상의 경우도 동일한 방식으로 특징점을 추출하게 된다.Multiple Point Signature에 의해 추출된 얼굴의 전역적 특징을 나타내는 특징점들은 여러 개의 1차원 Signature로 표현된다. 여러 개의 Signature로 표현된 각 얼굴 데이터의 특징들을 RBFN의 학습을 거친 후 거리 매칭을 이용하여 얼굴 인식을 수행한다.최종적으로 100명의 데이터베이스에서 총 5가지 포즈 변화에 대한 실험을 통하여 제안한 알고리듬이 기존의 국소적 영역으로 제한되었던 방법의 단점을 극복하였고, 93.8%의 인식률을 나타내었다.

홍채 인식을 위한 1차원 홍채 signature의 분석에 관한 연구

송명섭 연세대학교 대학원 2000 국내석사

본 논문에서는 1차원 홍채 signature에서 나타나는 홍채의 특징을 이용하여 홍채 인식을 수행하고자 할 때, 홍채 signature의 특징을 효과적으로 반영할 수 있는 가공 방법에 대하여 논하였다. 홍채 signature의 주파수 특성을 표현하기 위한 방법으로 퓨리에 변환, Gabor 필터링, 웨이블렛 변환을 제안하였다. 또한 동일인의 홍채 signature들의 일관성, 다른 사람의 홍채 signature들과의 변별력, 그리고 일관성과 변별력을 모두 고려한 우수도(Goodness)를 상관도(correlation)를 이용하여 정의하고, 이를 기준으로 각각의 방법을 비교·분석하였다. 기존의 홍채 인식 시스템은 2차원 영상의 텍스쳐(texture) 정보를 이용하여 홍채 코드를 생성, 인식한다. 이러한 영상을 사용하는 방법은 텍스쳐 정보를 추출하기 위해 사용되는 2차원 Gabor 필터의 설계가 어렵고 계산량이 많다는 단점이 있다. 보다 간단하고 신속한 인식을 위하여 1차원 홍채 signature를 인식에 이용할 수 있다. 홍채 signature의 미세한 변화에 대한 정보는 주파수 성분의 분석을 통해 얻을 수 있고 이를 위해서는 신호를 주파수 분석이 용이한 형태로 바꾸어 줄 필요가 있다. 실험을 통해서 홍채 영역 중 signature를 추출할 위치를 결정하였고, signature의 Gabor 필터링 및 Haar 웨이블렛 변환을 통해 일관성과 변별력이 높은 주파수를 선택하여 이 주파수 성분을 분석하였다. STFT는 신호의 주파수 특성이 어디에서 발생하고 있는지의 정보를 얻어낼 수는 있으나 윈도우의 크기가 고정되어 있기 때문에 효과적인 주파수 분석이 어렵다. 이에 비해 Gabor 필터링과 웨이블렛 변환은 신호의 특정 주파수 성분들이 위치에 따라 어떻게 나타나는지 분석이 가능하며, 분석하고자 주파수 성분에 따라 적절히 공간적 해상도를 조정할 수 있다. Gabor 필터링 및 Haar 웨이블렛 변환된 신호는 홍채 signature에 비해 일관성과 변별력을 높은 것을 확인했다. 이는 Haar 웨이블렛의 기저 함수들이 계단 함수의 형태를 가져 신호의 특성을 잘 반영할 수 있음에 반해 Gabor 필터는 신호의 필터링된 결과에 영향을 주기 때문이다. 따라서 Gabor 필터링보다는 Haar 웨이블렛 변환에 의해 만들어진 신호가 변별력이 높아 홍채 signature를 보다 높은 일관성과 변별력을 가지는 신호로 가공할 수 있는 제안된 가공 방법 중 가장 적절한 것임을 알 수 있었다. To perform iris recognition, the iris is changed to 1-D iris signature. In this paper, methods of efficient iris pattern transformation is discussed. To represent iris signature's frequency characteristics, Fourier transform, Gabor filtering, and wavelet transform are proposed. Considering the consistency between same person's iris and the discrimination between different person's iris, the goodness is defined by using correlation. Based on the goodness, three transform methods are compared and analyzed. To recognize one's iris, former iris recognition system creates iris code using texture information of the 2-D image. To extract texture information, 2-D Gabor filter is used. But the design of the filter is difficult and the computation amount is extremely large. For simpler and faster recognition, 1-D iris signature can be used. The detail informations of the iris signature can be acquired through frequency analysis. The signature should be transformed to make frequency analysis easier. The region to be extracted within the iris region is determined by experiments. By Gabor filtering and Haar wavelet transform, frequency with high consistency and discrimination is selected. The selected frequency is used for the analysis. STFT can obtain the information about where the frequency characteristics actually occur in the signal. But, It is difficult to analyze the frequency characteristics accurately because the size of window is invariable. In contrast, by Gabor filtering and wavelet transform, analysis of specific frequency components according to the position of the signal is possible and we can take appropriate space resolution with frequency variation. It was found out that the Gabor filtering and the wavelet transform has better consistency and discrimination than the iris signature. Because base functions of the Haar wavelet can represent the characteristics well because of their very simple shape like the step functions. So transformed signal by Haar wavelet transform is more discriminative than the signal by the Gabor filtering. As result, Haar wavelet transform was the most appropriate transform, among the proposed transform methods.

SigBox: Automatic Signature Generation Method for Fine-grained Traffic Identification

Yoon, Sung Ho 고려대학교 대학원 2015 국내박사

With the continual appearance of new applications and the frequent update of these applications, the need for automatic signature generation is emphasized. Although several automatic methods have been proposed, there are still limitations to adopt real network environment in terms of automation, robustness, and sophistication. To address this issue, we propose an automatic signature generation method, called SigBox, for fine-grained traffic identification. This system extracts three types of signature such as content, packet, and flow signature using a modified sequence pattern algorithm. The flow signature, final result of this system, consists of a series of packet signatures, and the packet signature consists of a series of content signatures. The content signature means distinguishable and unique substring of packet payload, and consists of a series of characters or hex values. Using the modified sequence pattern algorithm, we can improve system performance in aspect of automation and robustness. Also, the proposed method can generate sophisticated signature for fine-grained traffic identification by using flow-level features beyond ones of packet-level. In order to prove the feasibility of our proposed system, we present experimental results based on ten popular applications after defining three metrics such as redundancy, coverage, and accuracy. Also, we show the quality of signature compared to existing methods.

Strong Unforgeable Online/Offline Signature with the Offline Token Security

김기탁 고려대학교 정보경영공학전문대학원 2014 국내박사

The digital signature is one of the most important primitive for the cryptographic purpose such as the integrity and authentication. Researchers in modern cryptography try to design practically efficient and provably secure schemes. To get the reasonable efficiency, the designer tries to reduce the computation, storage requirement, and transmission bandwidth. To provide the security of the scheme, the prover has to set the security model of the scheme. In some special situation that the user has to rapidly response an ask of the user’s signature, it is required to decrease the time and computing costs to sign a message. In other case, the device, such as the smartcard, has a low computational ability. Thus, it is not able to generate a signature if the signature schemes contains some complex computation. In that case, if the parts, which requires the major computing power to sign the message, could be generated at the manufacturing step of the device, it helps to apply the signature algorithm to the low power device. However, the usual signature algorithm may be not possible to pre-compute the computationally intensive part. A special signature is required suitable for this situation. Online/offline signatures can solve the above situations. It contains two phases. In the (first) offline phase, a signer generates the offline token without the message that needs to be signed. In the (second) online phase, the signer uses the offline token to generate the final signature when the message is received. The offline step is relatively slow whereas the online step is fast. In the offline phase, an offline token is generated and stores in the device which performs online/offline signature scheme. To the best of our knowledge, all previous online/offline signature schemes assume that the offline tokens are stored securely. In real applications, however, this assumption does not hold rigidly. For example, smartcards may be used in the application of online/offline signatures, but these devices lack sufficient computational power. Thus, a smartcard performs the offline step when it is used to access a terminal if it has insufficient computational power. Alternatively, the offline tokens may be stored in the smartcard when it is manufactured. A smartcard has secure storage, but maximum storage is only 0.1 megabytes. In the most efficient online/offline signature schemes, the size of an offline token is almost 1,200 bits. Therefore, over 1.4 megabytes of secure storage are required in a smartcard to store 10,000 offline tokens. This means that sufficient offline tokens cannot be stored on a smartcard. To the best of our knowledge, all previous results are forgeable if an offline token is exposed. A smartcard is very small device, which makes it easy to lose or steal. Thus, the previous security model used for online/offline signatures does not reflect the real environments where online/offline signatures are applied. This thesis studies the security of online/offline signatures. A new security model for online/offline signatures, called offline token leakage-resilient model, is proposed. In this model, an attacker has an extra ability, i.e., he/she can issue offline token leakage queries during the study phase, and obtains the offline tokens. By allowing offline token leakage query, this new model reflects the real environment of the smartcard. To show the existence of secure online/offline signature scheme under the proposed model, a generic construction for online/offline signature is also proposed. Finally, the offline token leakage-resilient and strong unforgeable online/offline signature scheme is proposed.

On-line signature verification using local temporal shift estimated by the phase of Gabor filter

이종현 Graduate School, Yonsei University 2002 국내박사

In this dissertation, an on-line signature verification method using temporal shift estimation is presented. Local temporal shifts existing in signatures are estimated by the differences of the phase outputs of Gabor filter applied on signature signals. In the proposed signature verification algorithm, an input signature signal undergoes preprocessing procedures including smoothing, size normalization and skew correction, and then it's feature profile is extracted from the signature signal. A Gabor filter with predetermined center frequency ω is applied on the feature profile, and a phase profile is extracted using the phase output. The feature profile and the phase profile are size normalized and quantized so that a signature code of fixed size is generated. The temporal shifts existing between two signatures are computed from the differences between the two phase profiles, which are divided by the center frequency ω. The information about the temporal shifts is used as offsets for comparing two feature profiles. Two kinds of dissimilarity measures are proposed. Temporal Dissimilarity is a measure reflecting the amount of total temporal disturbance between two signatures. And the difference between the two signature feature profiles are computed at each corresponding point pair and is accumulated into Temporally Arranged Feature Profile Dissimilarity. The decision boundary is represented as a straight line in the dissimilarity space whose two axes are the two dissimilarity measures. The slope and the position of the decision boundary are computed using the distribution of the dissimilarities among the sample signatures involved in the enrollment procedure. Through experiments conducted with 4 kinds of center frequencies of Gabor filter and various feature profiles, the performances and the applicability of the proposed signature verification algorithm are validated. The proposed algorithm shows equal error rates about 3% lower than the conventional approaches. When multiple prototype signatures were selected from 12 training samples, the minimum equal error rate was found to be 2.2%. The proposed algorithm could compare 6563 pairs of signatures and generate 540 signature pairs. And the necessary data size was 512 Bytes long.